Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
Graph and Network Theory
Math 137A
HOMEWORK 2
8 PROBLEMS
DUE: WEDNESDAY, FEBRUARY 2, 2011
(1) Let G be a simple graph where the vertices correspond to each of the squares of an 8 × 8 chess board and where two squares are adjacent if, and only if, a knight can go from one square to the other in one move. What is/are the possible degree(s) of a vertex in G? How many vertices have each degree? How many edges does G have?
(2) Let G be a graph with n vertices and exactly n − 1 edges. Prove that G has either a vertex of degree 1 or an isolated vertex.
(3) Prove that if a graph G has exactly two vertices u and v of odd degree, then G has a u, v-path.
(4) Let G be a simple graph. Show that either G or its complement G is connected.
(5) Are any of the graphs Nn, Pn, Cn, Kn and Kn,n complements of each other?
(6) Show that if a simple graph G is isomorphic to its complement G, then G has either 4k or 4k + 1 vertices for some natural number k. Find all simple graphs on four and five vertices that are isomorphic to their complements.
(7) The complete bipartite graphs K1,n, known as the star graphs, are trees. Prove that the star graphs are the only complete bipartite graphs which are trees.
(8) A graph G is bipartite if there exists nonempty sets X and Y such that V (G) = X ∪ Y , X ∩ Y = ∅ and each edge in G has one endvertex in X and one endvertex in Y . Prove that any tree with at least two vertices is a bipartite graph.