Exercise 27, page 666. The solution is on page S-60.
What is the definition of a Hamilton cycle in a simple graph?
What does it mean for two simple graphs to be isomorphic?
A simple graph is k-regular if all of its vertices have degree k. How many edges does a 50-regular graph with 100 vertices have?
Consider the set S of the people at at party. Let h(p) be the number of people that person p has shaken hands with at the party. Assume that no person shakes hands with himself or herself. Show that the sum for all p in S of h(p) must be even.
Suppose that m and n are positive integers where m ≤ n. Show that the subgraph induced by any set of m vertices of Kn is a complete graph.
How many nonisomorphic simple graphs are there that have 3 vertices? (That is, how many 3-vertex graphs can be found where no two of those graphs are isomorphic?)
Let G be a directed graph and let u and v be two vertices of G. Let S(x) be the strongly connected component of G that contains x. Show that S(u) and S(v) are either the same set or are disjoint sets.
Suppose that G = (V, E ) is a simple graph. Recall that N(S) is the neighborhood of set S of vertices. Suppose that A and B are subsets of V. Show that N(A ∪ B) = N(A) ∪ N(B).
Show a simple graph G = (V, E ) and two subsets A and B of V, where N(A ∩ B) ≠ N(A) ∩ N(B).
Suppose that G and H are isomorphic simple graphs. Show that, if G is bipartite, then H is also bipartite.
Wn is the wheel graph with n vertices, excluding the central vertex. Suppose that n is even. What is the smallest integer k such that Wn can be colored with k colors?
What does Kuratowski's theorem say?
Suppose that G is a connected planar simple graph with 6 vertices, each of degree 4? Into how many regions does a planar embedding of G divide the plane?
Suppose that A is the adjacency matrix of simple graph G. Let B = A2. What information does the entry at row i, column j in B provide?