Introduction to Graph Theory - Second Edition

by Douglas B. West

Supplementary Problems Page

This page contains additional problems that will be added to the text in the third edition. Please send suggestions for supplementary problems to west @ math.uiuc.edu.

Related pages

• Corrections (typos in notation, omissions from mathematical statements, etc.)
• Comments and updates (corrections to references, comments on proofs or exercises, etc.)
• Minor typos (errors in spelling, punctuation, etc.)
• Index page for Introduction to Graph Theory
• Index page for Math 412

Supplementary Problems by Section

Section 1.1

• (-) Count the isomorphism classes of subgraphs of the kite.
• (-) Prove that the Petersen graph has five independent sets such that each vertex appears in exactly two of these sets.
• Determine the independence number of the simple graph obtained from two disjoint copies of P₄ by making each endpoint of one copy of P₄ adjacent to each endpoint of the other copy of P₄.
• Determine whether the two graphs below are isomorphic (the cartesian product of two triangles, and another 4-regular 9-vertex graph in which every triangle has a vertex in a set of size 3 that induces a triangle)
• Determine which pairs among the graphs below are isomorphic (the Heawood graph with spanning cycle following a circle, the incidence graph of the Fano plane drawn as a bipartite graph, and the generalized Petersen graphs P(7,2) and P(7,3)
• Prove or disprove: For every natural number n there is at most one isomorphism class of n-vertex bipartite graphs in which every vertex has degree 3.
• Show that the two graphs below are isomorphic (the Chv\'atal graph on the left in Exr5.1.46 and the highly symmetric drawing of it having all vertices on a cycle)
• Prove that every graph can be represented by associating a natural number with each vertex so that vertices are adjacent if and only if their numbers have a common factor larger than 1
• Compute the girth of the graph on the left in Exr1.1.20.
• Let G be a graph of girth at least 6. Prove that if every vertex of G has degree k, then G has at least 2k^2-2k+2 vertices. (Comment: There is such a graph with exactly 2k^2-2k+2 vertices when k-1 is a power of a prime.)
• Let G be the Petersen graph, expressed as the graph of the disjointness relation on the set of pairs in [5]. Obtain G' from G by adding five vertices called 1, 2, 3, 4, 5, with vertex j adjacent to vertex \{i,j\} for all j\in[5]-\{i\}, plus one vertex \nul ajdacent to \{1,2,3,4,5\}. Note that every vertex of G' has degree 5. Let H be the graph whose vertices are the binary 4-tuples, with two 4-tuples adjacent if they differ in exactly one coordinate or in all four coordinates. Prove that G' and H are isomorphic.
• A tetrahedron has four vertices and six edges. What must be done to turn it into the Petersen graph?
• Prove that the subgraph left by deleting the vertices of any 5-cycle in the Petersen graph is a 5-cycle. Prove that every 6-cycle contains two edges from one of these 5-cycles and one edge from the other.
• Detemine the number of maximum-sized independent sets of vertices in the Petersen graph.
• Determine the minimum number of vertices that must be deleted from the Petersen graph to reduce the independence number.
• Determine all the isomorphism classes of self-complementary graphs with five vertices.
• (+) The notion of self-complementary graphs can be generalized by saying that n-vertex graphs G_1 and G_2 {\it pack} if K_n contains edge-disjoint copies of G_1 and G_2. Prove that G_1 and G_2 pack if 2\Delta(G_1)\Delta(G_2) < n. (Sauer--Spencer [1978])
• (+) Let A be the adjacency matrix of a simple graph G.
  a) Prove that A is the incidence matrix of some simple graph if and only if G is 2-regular and has no 4-cycle.
  b) Determine the conditions under which A is the incidence matrix of G itself.
• The Mobius ladder M_k is the 3-regular graph obtained from C_2k by adding an edge joining each pair of diametrically opposite vertices on the cycle.
  a) For k=4, determine whether the graph obtained by deleting a diagonal edge from M₄ is isomorphic to the graph obtained by deleting one of the edges on the original cycle.
  b) For each k, determine all numbers that are lengths of induced cycles in M_k.
• (*) Let \sigma be an isomorphism from a graph G to its complement, viewed as a permutation of the vertices. Prove that the length of every nontrivial cycle of \sigma (that is, except fixed points) is a multiple of 4.

Section 1.2

• (-) Prove or disprove: For each natural number n, there is at most one isomorphism class of n-vertex bipartite graphs in which every vertex has degree 3.
• (-) Prove or disprove: Every Eulerian graph has no cut-edge.
• (-) Prove or disprove: Every Eulerian simple bipartite graph has an even number of vertices.
• (-) Let G be the complement of an odd cycle. Prove that G contains an odd cycle for which the two neighbors of each vertex are not adjacent in G.
• (-) Assign integer weights to the edges of K_n. Prove that the total weight on every cycle is even if and only if the total weight on every triangle is even.
• Assign integer weights to the edges of K_n. Prove that the total weight on every cycle is even if and only if the edges with odd weight form a spanning complete bipartite subgraph.
• For any graph G with k non-cut-vertices, let F(G) denote the graph obtained from G by adding k edges to new vertices of degree 1. Prove that if H is an induced subgraph of a G, then F(H) is an induced subgraph of F(G) (Tuza [2006])
• Let P be a path in an Eulerian graph G. Prove that G has an Eulerian circuit in which the edges of P appear consecutively (in the order on P) if and only if G-E(P) has only one nontrivial component. (suggested by Tao Jiang)
• Let G be a k-regular graph with k odd. Prove that G does not decompose into paths of lengths greater than k. (John Ganci)
• Let G and H be two disconnected graphs with vertex set [n]. Prove that there are two elements of [n] that lie in different components in both G and H.
• Let k and r be positive integers. Define G by letting V(G) be the set of integer k-tuples, with u and v adjacent if and only if \sum|u_i-v_i|=r.
  a) Prove that G is disconnected if r is even.
  b) Prove that G is bipartite if r is odd. (Furedi-Kang [2004])
• (addendum to Exercise 1.2.40) Is it true that P and Q also must have a common edge?
• Let G be a graph of girth g in which every vertex has degree at least k. Prove that if k\ge2, then G contains a cycle of length at least (g-2)(k-1)+2.
• Determine the minimum number of vertices in a graph in which the minimum length of an even cycle is r and the minimum length of an odd cycle is s. (Harary-Kovacs [1982])
• The graph "below" is known as the Heawood graph. Determine all lengths of cycles in this graph.
• The complement of a disconnected graph is connected (Exercise 1.1.10). For n\ge6, prove that the minimum number of edges that must be deleted from K_n to obtain a graph having no decomposition into two disconnected subgraphs is 4. (Hint: Use induction to prove the upper bound.) (Caro-Roditty [2002])

Section 1.3

• (-) Let G be a k-regular simple graph with n vertices. Determine the number of copies of P₃ in G.
• (-) Prove that \delta(G)+\Delta(G)\le n(G) when G is bipartite.
• (-) Prove or disprove: If G is an X,Y-bigraph, then \sum_{x\in X}d(x)=\sum_{y\in Y}d(y).
• Prove or disprove: Every simple Eulerian graph with at least three vertices has at least three vertices with the same degree.
• (add to Exr1.3.21) Count the 4-cycles in K_m,n.
• Prove that there are exactly three isomorphism classes of 3-regular simple graphs with 8 vertices.
• An all-odd graph is a graph in which every vertex degree is odd. Prove that every wheel with an even number of vertices decomposes into three spanning all-odd graphs.
• Prove that if a 3-regular graph has a decomposition into paths, then the average length of the paths is at most 3. (Galvin)
• Prove that a k-regular graph has no decomposition into paths of length exceeding k if k is odd.
• Let G be an n-vertex graph with \delta(G) > n/4 and no cut-edge. Barat and Thomassen proved that if also e(G) is divisible by 3, then G has a decomposition into claws. Prove that minimum degree n/4 is not sufficient by considering graphs formed from 4 K_n/4 by adding one edge joining each pair of components.
• Determine whether every 3-regular triangle-free connected simple graph with eight vertices is isomorphic to the 3-dimensional cube Q₃.
• Determine whether there is a 4-regular graph with nine vertices that is not isomorphic to its complement.
• (+) For k\in\NN, let D(k) denote a list of 4k integers consisting of 2k copies of 3k-1 and 2k copies of k.
  a) Prove that if k<3, then every graph with degree list D(k) is self-complementary. (Hint: Describe all isomorphism classes of 3-regular bipartite graphs with 12 vertices.) (based on a communication from Josh Brownfield)
  b) Prove that if k>4, then some graph with degree list D(k) is not self-complementary.
• (+) Suppose that the vertices of Q_k can be partitioned into two sets A and B of equal size such that each set induces a connected regular subgraph, in which the degree are j and k-j, respectively. Prove that j=k/2. For j=k/2, find a construction (by induction on k) that works. (T. Biyikoglu)
• If an n-vertex simple graph has n-1 distinct vertex degrees, then which degree is repeated?
• For each positive integer k, determine whether there exists a simple graph having exactly i vertices of degree i for all i\in[k] and no other vertices.
• Prove or disprove: For every graph G, there is a partition of V(G) into two nonempty sets such that each vertex has at least half of its neighbors in its own set in the partition.
• Given a graph G, let H be a spanning bipartite subgraph of G with the maximum number of edges. Let X,Y be a bipartition of H. Prove or disprove: If v\in X, then it must hold that in the complement of G at least half of the neighbors of v lie in X.
• Prove that a graph whose vertex-deleted subgraphs are all trees is reconstructible.
• (!) Determine the minimum number of edges in a maximal triangle-free n-vertex simple graph.
• (!) Let H be a simple graph with n vertices. Prove that if n > k and e(H) > (k-1)(n-k/2), then H contains a subgraph with minimum degree at least k. (Bollobas [1978, pxvii])
• (+) Determine the largest number of edges in a bipartite subgraph of the Odd Graph O_k. Generalize to the Kneser graph.
• (!) Stronger version of Mantel's Theorem.
  a) For a vertex v in a graph G, let f(v) be the maximum size of an independent set contained in N(v). Prove that \sum_{v\in V(G)} f(v)<=\floor{n(G)^2/2}, and determine which graphs achieve equality. (Hint: Consider a maximum independent set in G.
  b) Use part (a) to obtain Theorem 1.3.23 (Mantel's Theorem). (Galvin [1999 MAA 10761 and JGT 38 (2001), 170-176])
• Given an X,Y-bigraph G and edges x₁y₁ and x₂y₂ with x₁,x₂\in X and y₁,y₂\in Y, say that a bridging operation deletes x₁y₁ and x₂y₂ and adds two new vertices x₃ and y₃ with N(x₃)={y₁,y₂,y₃} and N(y₃)={x₁,x₂,x₃}. Prove that every 3-regular bipartite simple graph can be obtained from a graph whose components are isomorphic to K_3,3 by repeated bridging operations. (Kotzig [1966])
• For each k\in\NN, construct a connected 3-regular graph G_k with 6k vertices such that no induced subgraph is a cycle whose length is twice an odd number. (Hint: First construct an example that is not connected.)

Section 1.4

• (-) Determine the smallest tournament that is not strongly connected and has no source or sink.
• (!) Prove that if e(H)/n(H)\le d for every subgraph H of a graph G, then G has an orientation in which every vertex has outdegree at most d. (Hint: Iteratively modify an arbitrary orientation to obtain a desired orientation.) (Tarsi [1981])
• Given an alphabet of size k, prove that there exists a cyclic arrangement of 2k^l-1 letters from the alphabet such that all the strings of l consecutive letters are distinct and all possible strings of l-1 consecutive letters appear. (Fon-Der-Flaass)
• Let G be a simple n-vertex digraph, and let A be its adjacency matrix. Show how to determine whether G has a vertex with indegree n-1 and outdegree 0 by consulting fewer than 2n entries in A
• Let G be a directed graph. Prove that G decomposes into two acyclic digraphs.
• (!) Let T be a tournament. Prove that \sum_{v\in V(T)}{d⁺(v)\choose 2}=\sum_{v\in V(T)}{d^-(v)\choose 2}. (Hint: Think of a set of subgraphs that each side counts.)
• (!) Let T be an n-vertex tournament.
  a) Prove that the number of 3-cycles in T is {n\choose 3}-\sum_{v\in V(T)}{d^+(v)\choose 2}. (Kendall-Smith [1940]) (Kendall, J.B. and Smith, B.B., 1940. On the method of paired comparisons. Biometrika 31, pp. 324-345)
  b) Given that n is odd, determine the maximum possible number of 3-cycles in T.
• Consider a sports league with five teams in which each pair plays a match. Winning a match earns a team three points, and a tie gives one point to each team. If the point totals at the end of the season for a,b,c,d are 9,8,4,3, respectively, then what are the possible point totals for e? (Hint: Begin by considering the possible won/loss/tie records for a and b.)
• (*) Prove that a digraph with no even cycle has at most one kernel.
• Determine the least positive integer n (other than 1) such that in some n-vertex tournament each vertex can reach every other vertex by a path of length exactly 2. (Hint: Show that each indegree and outdegree must be at 3. Comment: Almost every tournament has this property; see Section 8.5.)

Section 2.1

• (-) Prove or disprove: If e is an edge of a connected loopless graph G, then e belongs to some spanning tree of G.
• (-) Prove that a connected simple graph G is a tree if and only if for every v\in V(G), the number of components of G-v equals d_G(v)
• (-) Let G be a tree. Prove that there is a partition of V(G) into two nonempty sets such that each vertex has at least half of its neighbors in its own set in the partition if and only if G is not a star.
• (-) Let H be a subgraph of a simple connected graph G. Prove that G has a spanning tree containing H if and only if H is a forest.
• (-) Let H be the square of a graph G. Prove that for every vertex v in H, the neighborhood of v in H induces a connected subgraph in G.
• Lemma 2.1.3 is not needed to prove that A implies B and C in Theorem 2.1.4. Use Corollary 2.1.5a (which itself needs only Theorem 1.2.14) to prove that every n-vertex tree has exactly n-1 edges. (Suggested by a student of Gerard Chang)
• Let G be a forest with k nontrivial components. Let U be the set of vertices in G that have degree at least 2. Prove that G has 2k+\sum_{u\in U}[d(u)-2] leaves.
• Let G be a graph containing k edge-disjoint spanning trees, and let e₁,...e_k be distinct edges in G. Prove that G has edge-disjoint spanning trees T₁,...T_k such that e_i\in T_i for 1<i<k.
• Let G be a graph such that the degrees of any two vertices that are distance 2 apart sum to at least 2k. Prove that G contains every tree with k edges. (T. Jiang)
• Let T and T' be trees with n vertices. For 1\le j \le n-1, let a_j and b_j denote the number of vertices of degree j in T and T', respectively. Prove that \sum_j [j (a_j-b_j)]= 0.
• Prove that the following properties are equivalent for a graph G.
  a) G is a forest.
  b) The intersection of any two intersecting paths in G is a path.
  c) For a family of pairwise-intersecting paths in G, the greatest common subgraph is a path with at least one vertex.
• (!) Prove that a graph G is acyclic if it has at least three vertex-deleted subgraphs that are acylic. (Myrvold [1990])
• (!) Determine the maximum number of cut-edges in a 3-regular graph with n vertices. (Choi--O [2008])
• Let S be a set of k+1 vertices in P_n. Prove that for some pair of vertices in S, the distance between them is a multiple of k.
• Prove that there is a 16-vertex 5-regular graph with diameter 2.
• Prove that there is a 16-vertex tree with maximum degree 4 and eight vertices in each partite set that is not a subgraph of the 4-dimensional hypercube Q₄.
• Let P be a maximal path in a graph G, and let x and y be the endpoints of P. Prove that if d(x,y) > 2, then d(x,y)\le l+2-d(x)-d(y), where l is the length of P. (Comment: This extends Exr2.1.10.) (Tracy [2000])
• Determine the minimum radius among the spanning trees of the k-dimensional hypercube
• Determine the average distance between points in the k-dimensional hypercube Q_k (averaged over all pairs of points)

Section 2.2

• (-) Find the tree whose Prufer code is (2,3,4,4,3,2,1,6,5).
• (-) Add to Exr2.2.1 another case: "every value that is used appears exactly twice"
• (-) Add a second example to each of Exr2.2.2 and Exr2.2.3.
• Count the spanning trees in a graph that is the union of a k-cycle and an l-cycle with one common edge.
• (addendum to Exr2.2.31) Prove or disprove: Every graceful labeling of a path is an up/down labeling.
• (-) Prove that every nontrivial graph has an even number of graceful labelings.
• Determine all $n$ such that $K_n$ decomposes into spanning trees.
• (!) Use the method of Prufer codes to show that the number of rooted forests with vertex set [n] whose roots are [k] is kn^n-k-1. That is, let S be the set of rooted forests on [n] with root set [k]. For F\in S, form a list by iteratively deleting the largest (nonroot) leaf and recording its neighbor, until only the roots remain. Prove that this establishes a bijection from S to [n]^n-k-1x[k].
• Show that a graceful graph may have a non-graceful component, and show that a graph with all components graceful need not be graceful. (Ganci)
• Prove that every graceful forest is a tree. Prove that the smallest disconnected graceful graph has six vertices and five edges. (Ganci)

Section 2.3

• (-) In the given weighted graph (such as the graph in Exr2.3.23), present a list of edges in order that each algorithm below could add to form a spanning tree: (a) Kruskal's Algorithm. (b) Prim's Algorithm, starting from the vertex H.
• (-) Prove or disprove: In a weighted graph where the weight on each edge is its length, every tree generated by Dijkstra's algorithm is a minimum-weight spanning tree.
• (-) Prove or disprove: If in a weighted graph only one edge has the minimum weight, then that edge appears in every spanning tree.
• (-) Use a triangle with edges of weights 5, 4, and -3 to show that Dijkstra's Algorithm may fail when the edge weights are not all nonnegative.
• Suppose that in the hypercube Q_k, each edge whose endpoints differ in coordinate i has weight 2ⁱ. Compute the minimum weight of a spanning tree.
• Let v be a vertex in a connected graph G. Develop an algorithm for finding, among all minimum spanning trees of G, one that minimizes the degree of v. Prove that it works.

Section 3.1

• (-) Prove or disprove: For every vertex v in a graph G without isolated vertices, there is some maximum matching that saturates v.
• (-) Let A be a 0,1-matrix. A line in A is a row or a column. Two 1s in A are independent if no line contains both of them. Prove that the maximum number of pairwise independent 1s is equal to the minimum number of lines covering all the 1s in A.
• (-) Prove that the symmetric difference of two paths with the same endpoints decomposes into cycles. Use this to give an alternative proof that for every two vertices x and y in a tree G, there is a unique x,y-path in G.
• (-) Prove or disprove: A graph with no even cycles has at most one perfect matching.
• (Replacement for Exercise 3.1.14.) Count the perfect matchings in the Petersen graph by proving that every edge of the Petersen graph lies in exactly two perfect matchings. (Hint: Consider a drawing of the Petersen graph with an 8-cycle on the "outside".) (Galvin)
• (-) Prove that \alpha(G)\le n(G)-\delta(G) for every graph G.
• (-) Prove that \alpha'(G)\ge \delta(G)/2 for every simple graph G. How can the lower bound be improved when G is bipartite?
• (-) Prove that \alpha(G)\ge \Delta(G) for every triangle-free graph G.
• (-) Prove that \omega(G)\ge 1+\Delta(G)/2 for every claw-free graph G.
• (!) Let G be a k-regular bipartite graph, with k≥2. Prove that every edge of G appears in some perfect matching in G. Prove sharpness for k≥3 by constructing a k-regular bipartite graph having two edges that do not appear together in any perfect matching in G.
• (!) Let G be an X,Y-bigraph with \C X=\C Y=t, and fix r with r≤ t/2. Prove that if every matching of size r is contained in a perfect matching in G, then also every matching of size r-1 is contained in a perfect matching in G.
• (!) Let M be a matching in the hypercube Q_d. Suppose that the distance in Q_d between any two vertices in different edges of M is at least 3. Prove that M is contained in a perfect matching of Q_d. (Balogh [unpub.])
• Let G be a k-regular subgraph of K_n,n. Prove that every maximal matching in G has size at least kN/(2k-1). Prove that equality is achievable when 2k-1 divides n. (R. Udupa)
• Determine all graphs whose vertices can be labeled with positive real numbers so that the label on each vertex is the sum of the labels on its neighbors.
• Let G be a k-regular bipartite graph, with k\ge2.
  a) Prove that every edge of G appears in some perfect matching of G.
  b) Let G be the k-dimensional hypercube, with k\ge3. Prove that it is possible to delete a perfect matching from G such that in the remaining (k-1)-regular bipartite graph, there are two non-incident edges that do not extend to a perfect matching.
• Corollary 3.1.13 proves the Marriage Theorem from Hall's Theorem. Prove the Marriage Theorem using the Konig-Egervary Theorem instead.
• (Replacement for Exercise 3.1.23.) Stronger versions of Hall's Theorem. Let G be an nontrivial X,Y-bigraph satisfying Hall's Condition for X. Without assuming Hall's Theorem, prove the following.
  (a) There is a vertex x in X such that every edge incident with x belongs to some matching that saturates X. (Hint: Use induction on |X|.)
  (b) If d(x) >= k for all x in X, and |X| >= k-1, then there are at least k! matchings that saturate X. (Hall [1948], Halmos-Vaughan [1950])
• Construct a bipartite graph with no cut-edge and no cut-vertex that has an edge that appears in every maximum matching
• (!) Applications of Hall's Theorem.
  (a) Prove that every spanning subgraph of K_n,n with minimum degree at least n/2 has a perfect matching.
  (b) Let T be a set of k permutations of [n]. Prove that if k\le n/2, then there is some permutation of [n] that disagrees in every position with every member of T. Prove that if k > n/2, then there is some choice of T for which there is no such permutation. (Kezdy-Snevily; see Cameron-Wanless [2005])
• (!) Prove that if G is a spanning subgraph of K_n,n, then \alpha'(G)\ge \min{n,2\delta(G)}.
• Let G be an X,Y-bigraph with no isolated vertices, and suppose that d(x)\ge d(y) whenever xy\in E(G) with x\in X and y\in Y. Prove that G has a matching saturating X. Use this to show that the family of subsets of [n] can be partitioned into {n\choose n/2} inclusion chains. (A chain consists of sets A₁,...,A_m such that A₁\esub...\esubA_m.) (Galvin)
• Prove that in every n-vertex graph with no isolated vertices, every edge cover has size at least n/2. Prove that equality holds if and only if the graph has a perfect matching. (Comment: This problem is not restricted to bipartite graphs.)
• (!) Let r and d be integers with 0\le r\le d. Let G be a loopless graph in which every vertex has degree d or d+1. Prove that G has a spanning subgraph in which every vertex has degree r or r+1. (Hint: Reduce the problem to the case where r=d-1 and the vertices of degree d+1 form an independent set, and then apply Hall's Theorem.) (Thomassen [1981])
• Let G be a graph with no isolated vertices. Prove that G has an edge cover of size at most n(G)\Delta(G)/(1+\Delta(G)). For each choice of \Delta(G), show that the bound is best possible for infinitely many values of n(G).
• Given n red and n blue points in the plane, with no three on a line, prove that there is a matching of red points to blue points by straight line segments so that no two of the segments cross. (attribution?)
• (!) Let D be a digraph. Prove that there exist pairwise disjoint cycles in D such that each vertex of D lies in exactly one of the cycles if and only if |N⁺(S)|\ge |S| for all S\esub V(D). (Ore [1962])
• (!) Apply Hall's Theorem to prove the characterization of score sequences of tournaments in Exercise 1.4.35. That is, there is a tournament with outdegrees p₁,...,p_n if and only if for each k the k smallest of these numbers sum to at least {k\choose 2}, with equality when k=n. (Hint: Construct an X,Y-bigraph in which Y is the set of pairs from [n] and X consists of p_i copies of i for each i\in[n].) (C. M. Bang and H. Sharp, Jr., Score vectors of tournaments, J. C. T. B 26 (1979), 81-84)
• (!) Prove that if e(H)/n(H)\le d for every subgraph H of a graph G, then G has an orientation in which every vertex has outdegree at most d. (Hint: Apply Hall's Theorem to an X,Y-bigraph in which X=E(G) and Y consists of d copies of V(G). Comment: This is another proof for a supplementary problem for Section 1.4.) (Tarsi [1981])
• Define the m-deficiency \delta_m(v) and m-excess \epsilon_m(v) of a vertex v by \delta_m(v)=max{0,m-d(v)} and \epsilon_m(v)=max{0,d(v)-m}. Let G be a bipartite graph with partite sets X and Y of equal size. Prove that if there is a positive integer m such that \sum_x\inX\delta_m(x)+\sum_y\inY\epsilon_m(y) < m, then G has a perfect matching. (Ore [1962])
• For k\le m\le n, characterize the maximal subgraphs of K_m,n that have no matching of size k, and determine which have the most edges.
• Let G be an X,Y-bigraph with maximum degree D that does not have (m+1)K₂ as an induced subgraph. Prove that e(G) <= mD². (Faudree-Gy\'arf\'as-Schelp-Tuza [1989])
• Use \alpha(G)=\beta'(G) to prove that in a bipartite graph, every maximum stable set contains a vertex from every \alpha-critical edge.
• Let e be a cut-edge in a graph G. Prove that if e is \alpha-critical, then every maximum stable contains an endpoint of e. Prove that the \alpha-critical edges in a tree form a matching, and that this may fail if G is not a tree. (Zito [1991])
• Let v₁,...,v_n be a vertex ordering of G obtained by iteratively deleting a vertex that has maximum degree in the subgraph that remains. Let k=\ceil{\sum 1/(1+d_G(v_i)}. Prove that the last k vertices in the ordering form an independent set. (C-T [1991])
• A graph is F-saturated if it does not contain F, but adding any edge to it creates a graph that contains F. Prove that there is an F-saturated graph on n vertices having at most (\beta(F)-1)n+\Delta(F)n/2 edges, where \beta(F) is the vertex cover number of F. (Comment: K\'aszonyi--Tuza [1996] obtained a bound linear in n; F\:uredi gave this more precise result.)
• Let P(m,k) denote the generalized Petersen graph, defined as follows. Place m vertices each on two concentric circles. The vertices on the outer circle form a cycle. There is a perfect matching joining the outer vertices to the corresponding inner vertices (in order). Two inner vertices are adjacent if they are exactly k apart on the inner circle. For m>k, the result is a 3-regular graph. The Petersen graph is P(5,2).
  a) Prove that \al(P(3k,k)=(5k/2)-1.
  b) Prove that \al(P(m,k)\ge \FR k{k+1}m when m is divisible by k+1.
  c) Prove that \al(P(m,2)\ge 4m/5 when m is divisible by 5.
  (+) d) Prove that \al(P(m,2)\le 4m/5. (Cranston)
• (-) Prove that \gamma(G)\le\delta(G) when G is a graph with diameter 2.
• (-) Prove that a connected graph with domination number m has a connected dominating set of size at most 3m-2. Construct an example for each m to show that this bound cannot be improved.
• (-) Prove that a graph has diameter greater than 2 if and only if its complement has connected domination number at most 2.
• Find the domination number and the connected domination number of the Heawood graph.
• Let G be a graph with girth l. Prove that if \dlt(G)\ge 2 and l \ge5, then \gamma(G)\le\ceil{(n-\floor{l/3})/2}. (Brigham-Dutton [1990])
• Let G be a graph with girth l.
  a) Prove that if l \ge5, then \gamma(G)\ge\delta(G).
  b) Prove that if l \ge6, then \gamma(G)\ge2(\delta(G)-1).
  c) Prove that if l \ge7 and \delta(G)\ge2, then \gamma(G)\ge\Delta(G).
  d) Show that the bounds above are sharp for each value of \Delta(G). (Brigham-Dutton [1990])
• (+) Prove that \gamma(G)\gamma(\bar{G})\le n(G) for every graph G.
• (!) Let G be an n-vertex graph with minimum degree k. Prove that V(G) has a subset S of size at most \ceil{n/(k+1)} such that every vertex is within distance 2 of S in G. Show that this bound is best possible.
• (!) For the Kneser graph K(n,k), prove that \gamma(K(n,2))=\gamma_c(K(n,2))=3 when n\ge6 (Ivan\v co--Zelinka [1993])
• Domination in planar grids.
  a) Let G_m be the square grid with side-length m. That is V(G_m)={0,...,m}\times {0,...,m}, with (i,j) and (i',j') adjacent if and only if they differ by 1 in one coordinate. Determine lim_m\to\infty\ga(G_m)/n(G_m).
  b) Let H_m be the triangular grid with side-length m. That is, V(H_m)={(i,j,k)\inN₀³\st i+j+k=m}, with (i,j,k) and (i',j',k') adjacent if and only if they differ by 1 in two coordinates. Determine lim_m\to\infty \ga(H_m)/n(H_m).
  c) Obtain a similar result for the hexagonal grid (all bounded faces are hexagons).
• A p-dominating set is a vertex subset S such that every vertex outside S has at least p neighbors in S. Let \ga_p(G) denote the minimum size of such a set in a graph G.
  a) Prove that if \DLT(G)\ge p\ge 2, then \ga_p(G)\ge \ga(G)+p-2. (Fink--Jacobson [1985])
  b) Prove that if \ga_2(G)=\ga(G), then \dlt(G)\ge2 and every smallest 2-dominating set is an independent set. (Hansberg--Volkmann [2007])

Section 3.2

• (!) Prove that repeatedly applying the Augmenting Path Algorithm produces a maximum matching by using Theorem 3.1.10 instead of the vertex cover problem. That is, prove that when the algorithm stops with a matching M, the graph has no M-augmenting path.
• Let G be an X,Y-bigraph with |X|<=|Y|. Prove that G has a maximal path with an endpoint in Y. (Comment: This generalizes Exercise 2.1.29.) (Kundgen-Ramamurthi AMM 10920) (Hidden hint: Let M be a maximum matching, and consider an M-alternating path.)<\li>
• Prove that every tree has a maximum matching that covers every non-leaf vertex plus at least one leaf. (Lih-Lin-Tong [2006])
• Let G be an X,Y-bigraph. Use alternating paths to prove that there exists x\in X such that every edge incident to x belongs to some maximum matching. (Hint: Restrict to a subset of X that is saturated by some maximum matching. Comment: An inductive proof also proves Hall's Theorem; see the replacement for Exr3.1.23.)

Section 3.3

• (Extending Exr3.3.10) For all positive integers a,b such that a\le b\le 2a, construct a simple graph G such that \alpha'(G)=a and \beta(G)=b.
• Let M be a perfect matching in a 3-regular graph G. Prove that M contains every cut-edge of G. Generalize the result by obtaining the same conclusion with weaker conditions on G. (Luis Dissett observed that requiring G to be regular is superfluous; it suffices to have all vertex degrees odd.)
• For every k\in\NN that is even and at least 6, construct a k-regular connected simple graph having no subgraph in which (k-6)/2 vertices have degree k and the rest have degree k-1.
• Let G be a simple graph with \alpha'(G)=m. Prove that G has at most m(m-1) edges that belong to no maximum matching. Construct examples to show that this bound is best possible for every m. (Fred Galvin)
• Show that in a connected graph of even order, every vertex in a minimal Tutte set S has neighbors in at least three odd components of G-S. Conclude that every K_1,3-free graph of even order has a 1-factor.
• Without using any results on matchings in bipartite graphs, prove directly that every regular bipartite graph with positive degree satisfies Tutte's Condition (and therefore, by Tutte's Theorem, has a perfect matching). (R. Udupa)
• Let G be a 3-regular graph with n vertices.
  a) Determine the maximum possible number of leaf blocks in G, in terms of n.
  b) Prove that an n-vertex graph with b leaf blocks has a matching of size at least n/2-b/3. (Hint: Use the Berge--Tutte Formula.)
  c) Determine the minimum possible size of a maximum matching in G. (Comment: See Biedl et al.~[2004] for 3-regular graphs; Henning--Yeo [2007] generalized to regular graphs of higher degree.)
• Let G be a graph with 2m vertices that has exactly one 1-factor. Prove that e(G)\le m^2 and that this bound is sharp. (Hetyei)
• The graph "below" is known as the Heawood graph. Prove that every 2-factor in this graph is a spanning cycle.
• Let G be a regular graph of degree 2r-1. Prove that G decomposes into r factors such that all components of each factor are paths or cycles, and each vertex is an endpoint of a path in exactly one factor. For example, the Petersen graph has such a decomposition in which one factor is a perfect matching and the other consists of two 5-cycles.
• Prove that every vertex-transitive graph of even order has a 1-factor.
• Let S be the set of vertices having maximum degree in a graph G. Prove that if G[S] is bipartite, then G has a matching that covers all of S. (Kierstead)
• (+) For k\ge2 and g\ge 2 with g even, prove that there exists a k-regular bipartite (multi)graph with girth g. (Hint: To construct such a graph inductively, use a (k-1)-regular bipartite graph H with girth g and a bipartite graph with girth at least g/2 that is n(H)-regular. Comment: The additional requirement of bipartiteness strengthens the result of Erd\H{o}s--Sachs [1963]; see Exercise 1.3.16.) (Galvin)
• (+) Let G be a 2n-vertex graph vertices such that \C{N(S)}\ge\FR43\C S whenever S is a set of at most 3n/2 vertices. Prove that G has a 1-factor. (Hint: In proving that o(G-S)\le \C S for all S, consider the expansion properties of the set T consisting of the vertices in all the odd components of G-S except one.) (Anderson [1973])

Section 4.1

• (-) Let F be an edge cut in a graph G. Prove that F is the edge set of a bipartite graph.
• (-) Prove the converse of Lemma 4.1.22: If T is a rooted spanning tree of a graph G such that every edge of G is in T or joins a vertex to some ancestor in T, then T can be produced by a DFS from the root of T.
• (-) For n,k\in\NN such that n-k is nonnegative and even, show that the list consisting of k-1 copies of n-1 and n-k+1 copies of k is graphic but has no k-connected realization. (F. Jao)
• For each k, construct a graph of diameter 2 with minimum degree k and connectivity 1.
• (!) Construct a graph with degree list 5543333 that is 3-connected. Prove that it is 3-connected by using the Expansion Lemma and vertex splits.
• (!) Let G be an n-vertex graph with minimum degree n-3. Prove that if the complement of G contains no 4-cycle, then \kappa(G)=n-3.
• Let G be a bipartite graph. Prove that if \delta(G)>n(G)/4, then \kappa'(G)=\delta(G). Show that the inequality is sharp. L. Volkmann, An. Univ. Bucure\c sti Mat. 37 (1988), no. 1, 75--79.
• Let G be a bipartite graph. Prove that if \delta(G)\ge n(G)/3, then \kappa(G)=\delta(G). Show that the inequality is sharp. (Kostochka)
• Prove that when k is even, the k-connected Harary graph H_k,n has no edge whose contraction produces a k-connected graph. (Hint: Every edge lies in a triangle.)
• Let G be a simple graph whose connectivity and vertex connectivity are equal, other than a complete graph. Prove that every minimum edge cut consists of one edge incident to each vertex of a minimum separating set. (Ramras)
• a) Prove that every regular graph of even degree has even edge-connectivity.
  b) For even k and j with j\le k, let G be a k-regular graph formed from 2K_k+1 by deleting a matching of size j/2 from each component and adding a matching of size j joining the components. Prove that \kappa'(G)=j (Kostochka)
• Prove that \kappa'(G)=\delta(G) when G is a bipartite graph with diameter 3. (Plesnik-Znam [1989])
• Girth, diameter, and connectivity.
  a) Prove that \kappa(G)=\delta(G) when G is a graph with girth 5 and diameter 2. (Comment: Soneoka--Nakada--Imase--Peyrat [1987] proved the stronger and more general result that \ka(G)=\dlt(G) when G is a graph of girth g and diameter at most 2\CL{g/2}-3. Also, diameter at most 2\CL{g/2}-2 guarantees \ka'(G)=\dlt(G).)
  b) Construct an example to show that \kappa(G)<\delta(G) may occur when G has diameter 2 and girth 4. (Hint: There is such a graph having a 4-vertex set S such that G-S=2K_{3,3}.)
• Prove that a vertex v in a graph G is a cut-vertex of G if and only if v is the intersection of two blocks of G.
• A graph has cyclic edge-connectivity m if m is the minimum number of edges whose deletion leaves a disconnected graph with a cycle in each component. For m >= 6, prove that the double-wheel C_m-2\join 2K₁ is 4-connected and has cyclic edge-connectivity m. (Plummer [1972])
• Prove that a graph has no induced subgraph with three leaf blocks if and only if it is claw-free and net-free.
• Let G be a graph with minimum degree k. Prove that if [S,\Sb] is an edge cut of size less than k in G, then every dominating set of G has vertices in both S and \Sb. (Matula [1987])

Section 4.2

• (-) Let G be a 2-connected graph. Prove that if G has an ear decomposition such that the initial cycle has length at least l+1 and each added ear has length at least l, then the girth of G is at least l+1. Prove that the converse is not true (that is, provide a counterexample). (Kelmans)
• (-) Let G be a k-edge-connected graph, and let G' be obtained from G by adding a new vertex y with at least k neighbors in V(G). Prove that G' is k-edge-connected.
• Let a and b be nonadjacent vertices in a 2-connected graph G. Prove that if G-a-b is connected, then b lies on a cycle in G-a.
• Let s and t be vertices in a 2-connected graph G. Prove that the vertices of G can be linearly ordered so that each vertex outside {s,t} has a neighbor that is earlier in the order and a neighbor that is later in the order. (Hint: Use ear decompositions.)
• Let r be a vertex in a 2-connected graph G. Prove that G has two spanning trees T and T' such that for every v\in V(G), the r,v-paths in T and T' have no common internal vertices. (Hint: Prove that there is a vertex numbering and trees T and T' such that in T the numbers increase along paths from r and in T' they decrease along paths from r, except for r itself.) (Itai--Rodeh [1984])
• Let G be a 2-connected simple graph. Prove that in every ear decomposition of G, the number of ears (including the initial cycle) is e(G)-n(G)+1
• Let G be an n-vertex simple graph that is connected but not 2-connected. Let f(G) be the minimum number of edges that must be added to change G into a 2-connected graph. In terms of n, determine the maximum value of f(G), and determine all n-vertex graphs achieving the maximum.
• Prove that a graph G with at least three vertices is 2-connected if and only if for every two vertices x and y and every edge e, there is an x,y-path through e.
• Prove Proposition 4.2.13 directly by proving that in the larger digraph, for all u,v in the vertex set there is a u,v-path.
• Prove or disprove: If G is a 2-connected graph, then G contains a cycle C such that G-V(C) is connected.
• (a) Prove the following generalization of Theorem 4.2.17. If W is an x,y-cut in a graph or digraph G, then the minimum size of an x,y-cut contained in W is equal to the maximum number of x,y-paths with no shared vertices in W. (b) Use part (a) to give another proof of Theorem 4.2.19. (Hint: subdivide the edges.) (Galvin)
• Let G be a triangle-free graph with minimum degree at least k. Prove that if the graph obtained by contracting the edges of some matching in G is k-connected, then G also is k-connected. (Savage-Zhang [1998])
• For a set S of vertices in a graph G, suppose that \kappa_G(x,y) \ge k whenever x,y\in S. Prove that if |S|\le k+1, then the vertices in S lie on a single path in G. Show this cannot be guaranteed when |S| > k+1.
• Let G be a connected graph with at least k+1 vertices. Prove that G is k-connected if and only if whenever d(x,y)=2 there is a family of k pairwise internally-disjoint x,y-paths in G. (Li [1994], Naatz [2000])
• For k >= 2, prove that every k-connected graph with at least 2k vertices contains a cycle of length at least 2k. (Hint: Consider a longest cycle.)

Section 4.3

• Use network flows to prove Hall's Theorem.

Section 5.1

• (-) Prove or disprove: every proper coloring of an odd cycle uses distinct colors on some three consecutive vertices.
• Prove that \chi(G)\ge n(G)/[n(G)-\delta(G)] for every graph G.
• Construct an interval graph G and an interval representation of G such that greedy coloring with respect to increasing order of right endpoints is not optimal.
• Prove that a tree is an interval graph if and only if it is a caterpillar (Definition 2.2.17).
• The graph below (the graph formed by adding a matching joining a triangle to an independent 3-set) has an optimal coloring in which each color is used twice. Prove that this coloring cannot be produced by the greedy coloring algorithm. (Fon-Der-Flaass)
• Construct a graph with nine vertices having an optimal coloring that cannot arise via greedy coloring. (Fon-Der-Flaass)
• In terms of the numbers of vertices and edges in a graph G, determine the number of vertices and edges in the cartesian product of k copies of G.
• For each k\in\NN with k\ge 2, construct a k-chromatic graph having no optimal coloring using a color class of size \alpha(G).
• Let G be a graph with mn vertices that decomposes into mK_n and nK_m. Prove that G\isom K_m\cart K_n. Construct infinitely many examples to in which F and H are graphs and a graph with n(F)n(H) vertices decomposes into n(H) copies of F and n(F) copies of H without being isomorphic to F\cart H.
• Let G be the intersection graph of a finite family of squares in the plane that are translations of a single square. Prove that G has a vertex whose neighborhood can be partitioned into at most two cliques. Conclude that \chi(G) <= 2\omega(G)-1.
• Prove that every graph G has a vertex partition into at most \CL{(\Delta(G)+1)/(k+1) classes such that each class induces a k-degenerate graph.
• Suppose that every edge of a graph G lies in at most k cycles. Prove that G is (2\sqrt k)-degenerate. (Hint: Consider an endpoint of a maximal path.) (Jiang-West)
• Let G be a graph in which no vertex lies on as many as {k\choose 2} odd cycles. Prove that G is k-colorable. (Comment: This generalizes the statement that graphs without odd cycles are 2-colorable.) (Locke [2004])
• Prove that every digraph D has a path with at least n(D)/\alpha(D) vertices. Conclude the Erdos-Szekeres Theorem. (Schmeichel)
• (immediately following Exr5.1.25) (+) We define a graph modeling perpendicular directions in space. The vertex set of G is the set of points on a sphere centered at the origin in R³ (this is an infinite graph). Make points p and q adjacent if the lines from the origin through p and through q are perpendicular. Determine \chi(G). (Christian Blatter [1999, MAA 10769])
• Let k be an odd integer at least 3. Prove that the cycle of length \CH k2 can be properly k-colored so that for every two color classes, there are adjacent vertices with these colors. (Comment: For a graph G, the achromatic number is the maximum number of colors in a proper coloring of G such that all pairs of colors appear on adjacent vertices.)
• (!) The Kneser graph K(n,k) is the disjointness graph of the k-element subsets of [n]. That is, the vertex set consists of all k-element subsets of [n], and two vertices are adjacent if they are disjoint k-sets. For example, the Petersen graph is K(5,2). Prove that \chi(K(n,k))\le n-2k+2 by covering the vertices with n-2k+2 independent sets. Prove that this is optimal when n=2k+1. (Comment: Lov\'asz [1978] proved Kneser's conjecture that always \chi(K(n,k))=n-2k+2.)

Section 5.2

• Prove that every triangle-free graph is a subgraph of a regular triangle-free graph with the same chromatic number. (Comment: Thus for every k there is a regular triangle-free graph with chromatic number k.)
• Determine the minimum number of edges among k-chromatic graphs with n vertices and minimum degree at least 2. Repeat with minimum degree at least 1.
• Prove or disprove: For every graph G, \chi(G)\le\omega(G)+n(G)/\alpha(G).
• Prove that \chi(G) \le 1+\max_{H\esub G}\kappa'(H) for every graph G. (Matula [1969])
• Prove that the graph below is 4-critical, thereby showing that a k-critical graph need not be (k-1)-connected. [graph is 7-vertex application of Hajos construction to two copies of K₄]
• Prove that 11 is the smallest number of vertices in a triangle-free 4-chromatic graph.
• For k\in\NN, prove or disprove: When the Hajos construction is applied to two k-degenerate graphs, the result is a k-degenerate graph.
• Determine the maximum value of the minimum degree of an n-vertex k-colorable simple graph. Use this to find the maximum possible value of \delta(G)/\chi(G) when G is an n-vertex simple graph.
• Let G be a graph not containing K_r+1. Prove that \chi(G)\le rn^1-1/2r-1.
• Alternative proof of Lemma 5.2.15. Given G,X,Y,H as in Lemma 5.2.15 and its proof, let F be the complement of the auxiliary bipartite graph H. Use Corollary 3.1.24 to prove that F is k-colorable, and from this prove Lemma 5.2.15. (W.G. Brown and H.A. Jung, Acta Math Hung [1969])
• Let A,B be a partition of the vertices of a graph G. Suppose that G[A] and G[B] are k-colorable and that |[A,B]|=m. Prove that \chi(G)\le k+m/k. (see Hakimi and Schmeichel, JGT 47 (2004), 217-225, although the idea is like that of Lemma 5.2.15)
• Replacement for Exercise 5.2.41 For m=k(k+1)/2-1, prove that K_m,m contains no K_2k-subdivision.
• Let G be a 2-connected graph containing no subdivision of K₄. Prove that G can be obtained from a single edge by a succession of subdivisions and doublings of single edges. (R.J. Duffin, J Math. Anal. Appl. [1965])
• A new type of combination lock uses card keys. The cards are numbered 1 through 100. The lock is set so that five of the cards are ``valid''. To open the lock, two valid cards must be inserted. Determine the minimum number of attempts (inserting a pair) that guarantees opening the lock. (Galvin)

Section 5.3

• (-) Find graphs G and H such that \chi(G\join H;k)=\chi(G;k)\chi(H;k), or show that no such graphs exist.
• In terms of the chromatic polynomial of G, determine the chromatic polynomial of G\join 2K_1.
• For n\in \NN, construct an n-vertex triangulation having more than 2ⁿ proper colorings from [4] and another having only 24 such colorings.
• Prove that if G is a chordal graph with at least one edge, then G has an edge e such that G-e is chordal. Prove that if H is a chordal graph that is not a complete graph, then H has two nonadjacent vertices x and y such that H+xy is chordal.
• Prove that a graph G is chordal if and only if every cycle C is the sum (symmetric difference) of n(C)-2 triangles in G. (Jamison [1987])
• Prove that a graph G is chordal if and only if the chromatic polynomials of all its induced subgraphs have only integer zeros. (Voloshin)
• Let G be a chordal graph. For each graph H, prove that \XPOL {G\join H}k=\XPOL Gk\XPOL H{k-\oG}.
• Prove that the radius of a chordal graph with diameter d is between d/2 and d/2+1 (Laskar-Shier [1983])
• Let G be a chordal graph with diameter d.
  a) Prove that G has two simplicial vertices whose distance is d. G is a clique if the radius is half the diameter. Construct a chordal graph in which the center is not a clique.
• Prove directly (without using the Perfect Graph Theorem) that the complement of a bipartite graph is perfect. (Hint: Apply a previous result about bipartite graphs.)

Section 6.1

• (-) Determine whether the graphs below are planar (variations on K_3,3).
• (-) Let G be a plane graph with dual G^*. What is the effect on the dual when an edge of G is subdivided? What is the effect when an edge of G is duplicated (that is, when another edge with the same endpoints is added)?
• (-) Let e be a cut-edge in a plane graph G. Prove that e appears twice in the boundary of a single face.
• Construct a simple 4-regular planar graph having an odd number of vertices.
• (-) Let G be a connected plane graph. Prove that the edge-connectivity of G* equals the girth of G.
• (-) Prove or disprove: Every 4-regular planar graph has a triangle.
• (-) Every outerplanar graph is 2-degenerate. Find a 2-degenerate graph that is not outerplanar.
• (-) Prove that a maximal planar graph is 3-connected. Prove that it does not have adjacent vertices of degree 3 if it has more than four vertices.
• Prove or disprove: The dual of a simple outerplanar graph cannot be a simple graph.
• Prove or disprove: Every triangulation in the plane is a chordal graph.
• Prove or disprove: Every triangulation in the plane has an even number of faces.
• Prove that every 2-connected planar graph has an ear decomposition in which ears are successively removed from the boundary of the external face of the remaining graph.
• Prove that a 2-edge-connected 3-regular plane graph is 3-connected if and only if no two faces share at least two boundary edges.
• (!) Prove that there is no Eulerian plane multigraph G with either property below (Hint: Consider the dual graph.)
  a) Every face of G has length 3 and G has a loop.
  b) One face of G has length 2 or 4 and the rest have length 3.
• (!) A 3-regular 3-connected plane graph in which 12 faces are 5-cycles and all other faces are 6-cycles is a fullerene. Let f₆ be the number of faces of length 6. For k\ge0, construct a fullerene with f₆=5k and a fullerene with f₆=6k+2. (Comment: Grunbaum and Motzkin [1963] (Canad. J. Math 15, 744-751) showed that there exist fullerenes with every number of 6-cycle faces other than 1.)
• (!) Prove that every plane graph with minimum degree at least 3 has a face with length at most 5.
• (!) Let l be the length of a longest cycle in a planar triangulation G. Prove that G has cycles of all lengths from 3 through l. (Balister; see Ryjacek [2003])
• Let G be the simple graph with vertex set v₁,...v_n such that v_iv_j\in E(G) if and only if |i-j|\le3. Determine whether G is a planar graph.
• Determine all n such that there exists a 4-regular simple planar graph with n vertices. (V. Chv\'atal, Planarity of graphs with given degrees of vertices, Nieuw. Arch. Wisk. 17 (1969), 47-60, and A. B. Owens, On the planarity of regular incidence sequences, J. Combinatorial Theory Ser. B 11 (1971), 201--212.
• (!) Prove that K₆ decomposes into two outerplanar graphs but K₇ does not. (Hint: Prove that the complement of any 7-vertex maximal outerplanar graph is not outerplanar.)
• (+) Prove that there is no 5-regular planar graph with 14 vertices. (Owens [1971])
• (+) Let G be a 3-connected plane graph in which no three faces have the same length. Prove that G has two faces each of lengths 3, 4, and 5 and no face at all of length at least 7. There are in fact four such graphs; construct one. (Hint: Consider the sum of the face lengths.) (Jorza [2001])
• Construct a simple Eulerian planar graph with minimum degree 4 in which no two vertices of degree 4 are adjacent.
• Construct a planar triangulation with n vertices that does not have three disjoint cycles.
• Let G be a maximal outerplane graph with at least three vertices. For each property below, determine whether it must hold for the dual graph G^*.
  a) outerplanar. b) not a simple graph. c) 3-colorable.
• Let G be a maximal outerplane graph. Prove that the number of vertices of degree 2 in G is two more than the number of triangles in G having no edges on the unbounded face.
• Let G be a plane graph with n vertices, m edges, and k components. Determine the number of faces of G.
• Determine the number of faces in a k-regular plane graph with n vertices
• The rhombicosadodecahedron is a polyhedron in which every vertex is incident to one triangular face, one pentagonal face, and two (opposite) quadrilateral faces. Determine the number of faces in the rhombicosadodecahedron.
• (!) Prove that every n-vertex planar graph with n+k edges has a cycle of length at most 2(n+k)/(k+2). For each k, construct examples to show that this bound is best possible for infinitely many n.
• (!) Prove that every n-vertex (simple) plane graph decomposes into at most 2n-4 edges and facial triangles. (Hint: Use induction on the number of facial triangles.)
• (!) Use Euler's formula to count the regions formed by n pairwise-crossing lines in the plane, where no three lines have a common point. (Hint: Modify the picture to obtain a finite plane graph.)
• Use Euler's formula to count the bounded regions formed by the diagonals of a convex n-gon, assuming that no three diagonals meet at a point. (Hint: Begin by finding a simple formula in terms of n for the number of intersections of diagonals.)
• Determine the minimum number of edges that must be removed from the 4-dimensional cube Q₄ to obtain a planar subgraph
• Determine the maximum number of edges in a planar subgraph of the k-dimensional cube Q_k.
• For sufficiently large k, find a nonplanar subgraph of Q_k with 11 vertices.
• A graph is cyclically k-edge-connected if no deletion of fewer than k edges disconnects it into two components that each contain a cycle. Prove that if G is a 4-connected triangulation, then G* is cyclically 4-edge-connected.
• (!) For a weak triangulation G, let B be the number of vertices on the unbounded face, and let I be the number of vertices in the interior, so that G has I+B vertices in total.
  a) Determine the numbers of edges and faces in G.
  b) Let T be a triangle with corners at integer lattice points in the plane. Prove that if no other lattice points lie on the boundary or in the interior of T, then T has area 1/2. (Hint: Use induction on the perimeter of the smallest lattice rectangle containing T.)
  c) A lattice polygon is a polygon whose corners are at integer lattice points in the plane. Let I be the number of lattice points in the interior and B be the number of lattice points on the boundary for a lattice polygon P. Prove Pick's Theorem, which states that the area of the region bounded by P is I+B/2-1. (DeTemple--Robertson [1974], Gaskell--Klamkin--Watson [1976])

Section 6.2

• (-) (added part to Exercise 6.2.2) Prove that the Petersen graph is nonplanar by proving that it is contractible to K₅.
• (-) For each graph below, determine whether it is planar.
  The graph obtained from K_4,4 by deleting a perfect matching.
  The graph obtained from K_4,4 by deleting a matching with three edges.
  The graph obtained from K₆ by deleting a perfect matching.
  The graph obtained from K₆ by deleting a matching M with two edges and subdividing the edge joining the two vertices not incident to M.<\li>
• Prove or disprove: Every bipartite graph with minimum degree at least 4 contains K_3,3.
• Prove or disprove: The union of any two paths is a planar graph.
• For n\ge 5, Let G be the graph whose vertex set consists of n points on a circle, with each vertex adjacent to the two nearest points in each direction on the circle. Prove that G is planar if and only if n is even.
• Let G be the graph obtained from the 3-dimensional cube Q₃ by adding an edge with endpoints (0,0,0) and (1,1,1). Find a planar embedding of G or show that it is nonplanar by using Kuratowski's Theorem.
• Prove that the square of C_n is planar if and only if n is even.
  or
  Give two proofs that C_n² is nonplanar when n is odd and at least 5.
  a) By using conflict graphs.
  b) By using Kuratowski's Theorem.
• Let G be an 8-vertex simple graph containing a subdivision of K_3,3. Determine whether it is possible that the complement of G also contains a subdivision of K_3,3.
• Let G be an 8-vertex simple graph having the same degree list as its complement. Construct examples to show that G and its complement can be both planar, both nonplanar, or one of each.

Section 6.3

• Let G be a triangulation with at least four vertices. Letting n_i be the number of vertices of degree i, prove that 3n₃+2n₄+n₅ \ge 12.
• Borodin proved that every planar graph has a proper 5-coloring such that the union of any two color classes induces a forest. Use this to prove the conjecture of ??? and Alon that every planar graph decomposes into five star-forests. (Hakimi-Mitchem-Schmeichel)
• (!) Prove that 7\le \nu(K₇)\le 9.
• (!) A planarity criterion.
  a) Prove that in every drawing of K₅ or K_3,3 in the plane, there are two nonincident edges that cross an odd number of times. (Hint: Prove that the number of such pairs is always odd.)
  b) Use part (a) to prove that if a graph G has a drawing in which every two nonincident edges cross an even number of times, then G is planar. (Hanani [1934], Tutte [1970])
• Use Exercise 6.3.28 and Kleitman's computation of \nu(K_6,n) to prove that \nu(K_7,7)\in{77,79,81}. (Comment: It is now known, via a computer-assisted search, that the answer is 81.)
• (*) Embed K₆ on the projective plane, and show that the dual is the Petersen graph.
• (*) Embed the Grotzsch graph on the projective plane so that every face has length 4.

Section 7.1

• (-) Prove or disprove: The line graph of every regular graph is regular.
• (-) Prove or disprove: If a graph G is Eulerian, then L(G) is Eulerian.
• (-) Let G be a regular graph of even degree. Prove that if \chi'(G)=\Delta(G), then e(G) is even.
• (-) Determine every connected graph G such that \chi'(G) < \chi(G) (Galvin)
• (-) Given integers r and d with 0\le r\le d, Use Vizing's Theorem to prove that every d-regular simple graph has a spanning subgraph in which every vertex has degree r or r+1. (Special case of Tutte [1978])
• (!) (Replacing 7.3.20): Prove that a 3-regular graph is 3-edge-colorable if and only if it is the union of two subgraphs in which every vertex has even degree.
• Prove that the graph obtained by deleting an edge from the Petersen graph is Class 2.
• (!) Chetwynd-Hilton [1986] proved that simple graphs with at most two vertices of maximum degree are Class 1. Use the join of K₃ and the complement of any matching to prove that this is sharp.
• Let G be the graph obtained by deleting one edge from the Petersen graph. Prove that G is Class 2 but has no overfull subgraph.
• Is it true that the line graph of every 3-regular simple planar graph is planar? What about 4-regular simple planar graphs?
• Determine when the cartesian product of two nontrivial connected line graphs is a line graph.
• (Addendum to Exr7.1.27.) Let G be the graph obtained from K_2m by subdividing one edge. Prove that G is a simple graph with fewest vertices among those with maximum degree 2m-1 and edge-chromatic number 2m.
• Prove that the line graph of G is chordal if and only if G is chordal. (Golumbic [1980], p101)
• (+) Let G be a 1-factorable graph with even degree and an even number of edges. Prove that L(G) is 1-factorable. (Jaeger [1974])
• (+) Prove or disprove: For sufficiently large k, if the edges of a complete graph are colored so that every vertex is incident to edges of at least k different colors, then there must be a cycle whose edges all have different colors.
• Alternative proof that chi'(G)=\Delta(G) when G is bipartite. Let G be a bipartite graph (multiple edges allowed). If \chi'(G)>\Delta(G), then G has a minimal subgraph G' such that \chi'(G')>\Delta(G). Prove that this cannot happen, by obtaining a proper \Delta(G)-edge-coloring of G' from a proper \Delta(G)-edge-coloring of G'-xy. (König [1916])
• (+) An interval coloring of G is a proper edge-coloring of G using integer colors such that at each vertex, the colors used on incident edges form an interval of integers. Prove that K_m,n has an interval coloring using m+n-\gcd(m,n) colors, and that no smaller number of colors suffices. (Hint: Combine solutions for the cases m=n and \gcd(m,n)=1 to construct a general solution.) (see Hanson--Loten--Toft [1998])
• Greedy edge-coloring obtains a proper edge-coloring using at most 2\Delta(G)-1 colors. For k\in\NN, construct a tree with maximum degree k and an ordering of its edges with respect to which greedy edge-coloring uses 2k-1 colors.
• A parity edge-coloring of a graph G is an edge-coloring such that along any path, some color appears an odd number of times. Prove that G is a subgraph of the k-dimensional cube Q_k if and only if G has a parity edge-coloring such that on every cycle, every color appears an even number of times. (K. Milans)
• With parity edge-coloring defined as above, let p(G) denote the minimum number of colors in a parity edge-coloring of G (no constraints on cycles). Prove that p(K_{2,3})=4 and p(K_5)=7.

Section 7.2

• (-) Determine whether the graph obtained by contracting one edge of the Petersen graph is Hamiltonian.
• (-) Prove that the Petersen is isomorphic to the graph obtained by identifying opposite vertices of the dodecahedron.
• (-) Prove or disprove: If d(x)+d(y)\ge n(G)+2 for adjacent vertices x and y in a graph G, then G is Hamiltonian if and only if G-xy is Hamiltonian.
• (-) Prove or disprove: If a graph G is Hamiltonian, then its line graph L(G) is Hamiltonian.
• Perfect matchings in the Petersen graph.
  a) Prove that every edge of the Petersen graph lies in exactly two perfect matchings. (Hint: Consider a drawing of the Petersen graph with an 8-cycle on the "outside".)
  b) Let A and B be two perfect matchings in the Petersen graph. Prove that some automorphism turns A into B. Use this to conclude that the Petersen graph has no 10-cycle. (Galvin)
• (!) The path cover number of a graph G is the minimum number of paths in a set of disjoint paths covering V(G) (thus the path cover number of a graph with a Hamiltonian path is 1). For each n that is a multiple of 18, construct a 3-connected 3-regular n-vertex graph with path cover number n/9.
• Prove that every k-regular k-edge-connected graph is 1-tough. (Comment: Hence every such graph also has a 1-factor.)
• (!) Let G be a bipartite graph with partite sets of size n/2 and minimum degree at least n/4+1. Prove that G is Hamiltonian. Show that this is sharp whenever 4 divides n by constructing for each such n an n-vertex non-Hamiltonian bipartite graph with minimum degree n/4. (Moon-Moser [1963])
• Use Example 7.2.14 (non-Hamiltonian graph with large degrees) and Remark 7.2.16 (characterization of G having spanning path by G\join K₁ having spanning cycle) to prove that Theorem 7.2.17 is best possible. (That is, produce a graph with large degrees that has no Hamiltonian path.)
• For k >= 2, the hypercube Q_k is a Hamiltonian bipartite graph. For k >= 3, prove that if one vertex is deleted from each partite set of Q_k, then what remains is also a Hamiltonian graph. (S. Locke)
• Construct a 3-connected 4-regular graph that is not Hamiltonian. (Hint: Modify the Petersen graph.)
• Given that an n-vertex graph with at least \CH{n-1}2+3 edges is Hamiltonian connected, show that for each vertex pair x,y there are x,y-paths of all lengths 2,...,n-1. (Jiang-West)
• (+) Prove that if a graph satisfies Chv\'atal's Condition, then its complement does not.
• Prove that every complete graph of odd order decomposes into Hamiltonian cycles. (Walecki)
• (!) Prove that a graph and its Hamiltonian closure have the same circumference.
• Use Theorem 1.4.26 to prove that the de Bruijn digraph D_n is Hamiltonian.
• (prior to Exercise 7.2.45.) Prove that every strong tournament is Hamiltonian. (Hint: Consider a longest cycle.) (Camion [1959])
• (addition to Exercise 7.2.45.) For 3\le m\le n prove that every strong n-vertex tournament has at least n-m+1 cycles of length m, and show that this is best possible. (Moon [1966])
• (!) A bipartite tournament is an orientation of a complete bipartite graph. Prove that a bipartite tournament has a spanning path if and only if it has a spanning subgraph whose components are cycles except that possibly one is a path. (Gutin [SIAM J Disc. Math 6 (1993), 270-273] proved that the statement holds also for all complete multipartite graphs.)
• (+) Prove that a bipartite tournament has a spanning cycle if and only if it is strongly connected and has a spanning subgraph whose components are cycles.

Section 7.3

• (-) Prove that every 2-edge-connected outerplane graph is 3-face-colorable.
• Let G be a maximal plane graph other than K₄. Prove that G is 3-face-colorable. (contributed by Michael Pelsmajer)
• Prove that the vertices of every planar graph can be 2-colored so that each color class induces an outerplanar graph. (Chartrand--Geller--Hedetniemi [1971])
• Let G be a 3-regular graph. Prove that G is 3-edge-colorable if and only if G is the union of two even subgraphs. (Perhaps replace 7.3.20)

Section 8.1

• Prove that if G is the complement of an interval graph and has girth at least 5, then G is acyclic and its longest path has length at most 3. (Kostochka)
• Let G be an interval graph with maximum degree k, and suppose that G has no k+1-clique. Prove that G has an interval representation in which the degree of the vertex whose interval extends farthest left is less than k. (Comment: This exercise proves that an interval graph is a regular graph only if its components are complete graphs.)
• Prove directly that every bipartite graph is strongly perfect.
• Let G be a partitionable graph, and let G' be a graph obtained from G by deleting \omega(G) vertices. Prove that \alpha(G')=\alpha(G).

Section 8.2

• (-) Let M be a matroid on E, and fix F\esub E. Prove that r_M.F(X)\le r_M(X) for all X\esub F.
• Let e be an element in a matroid M. Prove that if C is a circuit in M\cdot e, then C or C+e is a circuit in M.
• Let M be the hereditary system on E(K_n) whose independent sets are the edge sets of planar graphs. Determine whether M is a matroid.
• (!) Prove that the family of semi-independent sets of edges in a graph G is the family of independent sets of a matroid, where X is semi-independent if the spanning subgraph of G with edge set X has at most one cycle.

Section 8.3

• Prove that every 2-coloring of the edges of K₅ that has no monochromatic triangle consists of two monochromatic 5-cycles.
• Prove that every 2-coloring of the edges of K₆ forms at least two monochromatic triangles. (Hint (back of book): Start with the monochromatic triangle provided by Proposition 8.3.1.)
• Prove inductively that every graph with 2^k vertices has a clique Q and an independent set S such that |Q|+|S|=k+1. Conclude from this that R(k,k) <= 4^k.
• Let G be a graph in which every induced subgraph of order 2k has independence number k. Prove that n(G) < R(3,k+1)+3. (Comment: This places an upper bound of about k²/logk on n(G), but the best bound is linear.) (Andreas Brieden)
• Prove that R_k(p;r) > (p/e)k^{{p-1\choose r-1}/r}.
• (!) Prove that in every coloring of E(K_n), there is a triangle whose edges have three different colors or a monochromatic tree with n vertices. (Comment: This result generalizes the statement that the complement of a disconnected graph is connected.) (see Monthly Problem 6034, 82(1975), 529)
• Prove that in every 2-coloring of the edges of a complete k-partite graph with k\ge3, at least one color class forms a connected subgraph. This fails when k=2. (Caro-Roditty [2002])
• The zero-sum Ramsey number R(G,\ZZ_k) of a graph G such that k divides e(G) is the minimum n such that every coloring of E(K_n) with congruence classes modulo k has a copy of G on which the sum of the colors is a multiple of k. (Caro [1996] surveys results on zero-sum Ramsey numbers.)
  a) Prove that R(G,\ZZ_k) is well-defined when k divides e(G).
  b) Prove that R(K₃,\ZZ₃)=11.
• Prove that the bandwidth of the cartesian product of two n-cycles is 2n-1
• Define a graph on the infinite grid \ZZ^2 by making two vertices adjacent if they are consecutive along a line with slope in {0,\infty,1,-1} (thus the graph is 8-regular). Prove that for any set S having vertices from r rows and s columns, the boundary of S is at least 2r+2s+4. (Hint: The lower bound is immediate when S is an r-by-s rectangle. Comment: This lemma was applied in Balogh--Kaul [2007] to random geometric graphs.)

Section 8.4

• An odd representation of a graph G encodes each vertex as a binary k-tuple so that vertices are adjacent if and only if the dot product of their binary encodings is odd. Prove that every n-vertex graph has a binary encoding in n-1 dimensions. (Eaton-Grable)
• Let C and P be disjoint subgraphs of a graph G, with C being a k-cycle and P being a path. Prove that if G has no cycle whose length is congruent to 2 modulo k, then at most k edges have endpoints in both V(C) and V(P).
• Prove constructively that there is a graph with 3r vertices that is r-colorable but not r-choosable. (Hint: K_{3,3} is not 2-choosable.) (Kirov-Naimi)
• The graph theta(l₁,...,l_k) with branch vertices u and v is the union of k pairwise internally-disjoint u,v-paths with lengths l₁,...,l_k. The graph is bipartite if the k lengths have the same parity. Determine the choice numbers of the graphs theta(1,3,3), theta(3,3,3), theta(2,2,2), and theta(2,2,2,2).
• Let G be a digraph with minimum outdegree 3. Prove that G has two disjoint cycles. (Thomassen)
• Prove that K₄ is 3-edge-choosable
• (addition to Exr8.4.20) Show that the join of this graph with K_1 is 3-choosable. Thus it is possible that taking the join does not increase the list chromatic number.

Section 8.5

• Use the Second Moment method to prove that almost every graph fails Ore's sufficient condition for spanning cycles. (Palmer [1985, p84-85])

Section 8.6

• Given a graph G with vertices v₁,...,v_n, let a_k be the number of v_i,v_j-walks of length k. Show that for every choice of v_i and v_j, the sequence < a > satisfies the same recurrence of order at most n(G). (Emeric Deutsch observes this and wonders whether it has been noticed before.)
• Prove that the adjacency matrix of a forest is an invertible matrix if and only if the forest has a perfect matching. (Hint: Use Corollary 8.6.6.) (G. Royle)
• Prove that G is a strongly regular graph with parameters k,\lambda,\mu satisfying \mu=k if and only if G is a complete multipartite graph with partite sets of equal size.

Appendix B

• (-) Given that recognition of planar Hamiltonian graphs is NP-complete, show that it is NP-complete to find the maximum order of a common subgraph in two input planar graphs.
• Prove for all fixed k that it is NP-complete to determine whether an input graph has a k-factor that is connected.

More to Come!