Introduction to Graph Theory - Second Edition

by Douglas B. West

Supplementary Problems Page

This page contains additional problems, most of which will be added to the text in the third edition. Please send suggestions for supplementary problems to dwest @ illinois.edu.

Note: Notation on this page is now in MathJax. Right-click on any notation and choose "Settings" -> "Scale All Math" to adjust size. It is likely that some typos have been introduced by the conversion; please tell me about them.

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 (now diamond).
• Determine the independence number of the simple graph obtained from two disjoint copies of $P_4$ by making each endpoint of one copy of $P_4$ adjacent to each endpoint of the other copy of $P_4$.
• 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 that the number of isomorphism classes of $n$-vertex bipartite graphs in which every vertex has degree 3 is bigger for $n=8$ than for $n=6$.
• Show that the two graphs below are isomorphic (the Chvátal 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
• In the Petersen graph, determine the maximum size of an independent set and the minimum number of vertices whose deletion reduces that maximum size.
• 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$ adjacent 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.
• 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 three edges from one of these 5-cycles and one edge from the other.
• Let $e$ and $e'$ be non-incident edges in the Petersen graph. Prove that $e$ and $e'$ lie together in a $5$-cycle or in a $6$-cycle. Determine the number of pairs of each type.
• The Möbius 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. Determine all $k$ such that $M_k$ is edge-transitive.

Section 1.2

• (-) Prove or disprove: Every Eulerian graph has no cut-edge.
• (-) Prove or disprove: Every Eulerian simple bipartite graph has an even number of vertices.
• A {signed graph} is a graph plus an designation of each edge as positive or negative. A signed graph is {balanced} if every cycle has an even number of negative edges. Prove that a signed graph $V(G)$ is balanced if and only if $G$ can be partitioned into two sets $A$ and $B$ such that an edge of $G$ is negative if and only if it joins $A$ and $B$. (Cartwright--Harary [1956])
• Prove that every connected graph has a closed walk that traverses each edge exactly twice.
• 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$ 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$.
• Prove that the graph below (the prism over the 5-cycle) cannot be expressed as the union of two cycles.
• By Exercise 1.1.31, there is a self-complementary graph with $n$ vertices if and only if $n$ or $n-1$ is divisible by 4. Prove that for each such $n$ there is a self-complementary graph having a cut-vertex. (S. Gupta)
• 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.
• (+) For a graph $G$, let $c(G)$ be the least $k$ such that every edge lies in a cycle of length at most $k$ ($c(G)$ is infinite when $G$ has a cut-edge). For $n\ge 3$, prove that the minimum of $|E(G)|+c(G)$ among $n$-vertex connected graphs is $n+\lceil 2(n-1)^{1/2}\rceil $. (Butler--Mao [2007])
• 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 a decomposition into two disconnected subgraphs is 4. (Hint: Use induction to prove the upper bound.) (Caro-Roditty [2004])
• (+) The notion of self-complementary graphs can be generalized by saying that $n$-vertex graphs $G_1$ and $G_2$ pack if $K_n$ contains edge-disjoint copies of $G_1$ and $G_2$. Prove that $G_1$ and $G_2$ pack if $|E(G_1)||E(G_2)|\lt \CH n2$. (Comment: Sauer--Spencer [1978] showed this and also that they pack if $2\Delta(G_1)\Delta(G_2) \lt n$. (Sauer--Spencer [1978])

Section 1.3

• (-) Let $G$ be a $k$-regular simple graph with $n$ vertices. Determine the number of copies of $P_3$ in $G$.
• (-) Prove that $\delta(G)+\Delta(G)\le n(G)$ when $G$ is bipartite.
• (-) Prove that if $\delta (G)\ge 3$, then some cycle in $G$ is not an induced subgraph.
• (-) Prove or disprove: If $G$ is an $X,Y$-bigraph, then $\sum_{x\in X}d(x)=\sum_{y\in Y}d(y)$.
• (-) Let $G$ be an $n$-vertex graph in which every $k$-vertex induced subgraph is connected. Prove that $G$ has at least $n(n-1)/k$ edges.
• 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}$.
• Determine all the isomorphism classes of self-complementary graphs with five vertices.
• (!) For odd $k$, prove that in any decomposition of a $k$-regular graph into paths, the average length of the paths is at most $k$.
• For $n\ge2k$, determine the minimum number of distinct cycle lengths in an $n$-vertex graph with minimum degree $k$.
• Let $G$ be an $n$-vertex graph with $\delta(G)\ge n/4$ and no cut-edge. Barat and Thomassen [2006] proved that if also $n$ is sufficiently large and $e(G)$ is divisible by 3, then $G$ decomposes into claws. Prove that the degree requirement is sharp by considering graphs formed from $4 K_{n/4}$ by adding one edge joining each pair of components.
• Determine all triangle-free nonbipartite graphs $G$ in which the degrees of any two vertices sum to at least $|V(G)|-1$.
• Prove that every graphic list has a realization in which any specified vertex $v$ is adjacent to vertices whose degrees are the largest entries in the list other than its own. (Fulkerson-Hoffman-McAndrew [1965])
• An $n$-vertex simple graph has $n-1$ distinct vertex degrees. Determine the possible values of the repeated degree.
• 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.
• (!) A parity subgraph of a graph $G$ is a spanning subgraph $H$ such that $d_G(v)\equiv d_H(v)\mod 2$ for all $v\in V(G)$. Prove that every cut-edge of $G$ appears in every parity subgraph of $G$.
• 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$.
• (!) 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 \gt k$ and $e(H) \gt (k-1)(n-k/2)$, then $H$ contains a subgraph with minimum degree at least $k$. (Bollobás [1978, pxvii])
• (!) 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)\le\FL{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])

Section 1.4

• Determine the smallest tournament that is not strongly connected and has no source or sink.
• Prove that there is only one isomorphism class of Eulerian orientations of $K_5$
• (-) Let $D$ and $D'$ be acyclic orientations of a graph $G$ such that $d_D^+(v)=d_{D'}^+(v)$ for all $v\in V(G)$. Prove that $D=D'$.
• (!) 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.)
• In a signed graph, each edge is positive or negative. Thus each edge at a vertex contributes 1 or -1 to its degree, while loops contribute 2 or -2. Characterize the degree lists of signed multigraphs.
• 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$.
• 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 least 3. Comment: As $n$ tends to $\infty$, the fraction of $n$-vertex tournaments having this property tends to $1$.)

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 $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 $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.
• Prove that a graph whose vertex-deleted subgraphs are all trees is reconstructible.
• 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_1,\ldots,e_k $ be distinct edges in $G$. Prove that $G$ has edge-disjoint spanning trees $T_1,\ldots,T_k $ such that $e_i\in T_i$ for $1\le i\le k$.
• Prove that if the vertices of a regular graph with degree greater than 2 can be partitioned into two sets that each induce a tree, then the two sets have the same size (X. Lv)
• Let $s(v)$ be the sum of the distances from $v$ to all other vertices. Prove that in a nontrivial tree, the value of $s(v)$ has the same parity for all $v$ if and only if the number of vertices is even.
• 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)
• Prove that the following properties are equivalent for a graph $G$ (replacing Exercise 8.1.16).
  a) $G$ is a forest.
  b) The intersection of any two paths in $G$ that intersect is a path.
  c) The members of any pairwise-intersecting family of paths in $G$ have a common vertex.
• (!) Prove that a graph $G$ has at most one cycle if it has at least three vertex-deleted subgraphs that are acyclic. (Myrvold [1990])
• (!) Determine the maximum number of cut-edges in a 3-regular graph with $n$ vertices. (O--West [2010])
• 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$.
• Determine the maximum and minimum of the distance-sum (Wiener index) $D(G)$ over $n$-vertex connected graphs having $n$ edges.
• Prove that the complement of a regular graph with diameter at least 3 has diameter at most 2.
• 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_4$.
• 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)\gt 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])
• Let $G$ be a graph. Construct a graph $H$ such that the subgraph of $H$ induced by the center of $H$ is isomorphic to $G$. (Hartke)
• 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 Prüfer 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.
• (!) Let $G_{n,m}$ be the union of copies of $K_n$ and $K_m$ sharing two vertices. For example, $G_{3,3}=K_4^-$. Determine $\tau(G_{n,m})$. (Stolee)
• Use the Prüfer correspondence to count, for $n\ge 4$, the trees with vertex set $[n]$ having exactly three leaves.
• Determine all $n$ such that $K_n$ decomposes into spanning trees.
• (!) Use the method of Prüfer 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-1}\times [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 with no isolated vertex 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, every tree generated by Dijkstra's algorithm is a minimum-weight spanning tree.
• (-) Prove or disprove: In a weighted graph the edges of smallest weight appear in every minimum-weight 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^i$. Compute the minimum weight of a spanning tree.

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$.
• (-) 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 (simple) 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$.
• (-) Let $G$ be a connected graph. Prove that $G$ has a spanning tree $T$ such that $\alpha'(T)=\alpha'(G)$
• (-) A line in a 0,1-matrix is a row or a column, and two entries are independent if they do not lie in a common line. Prove that the maximum number of pairwise independent 1s in a 0,1-matrix equals the minimum number of lines that together contain all the 1s.
• (-) Let $A$ and $B$ be disjoint independent sets in a graph $G$, with $|A|=\alpha(G)$. Prove that $G[A\cup B]$ contains a matching of size $|B|$.
• (!) Let $G$ be a subgraph of $K_{t,t}$ having a perfect matching. For $r\lt t$, 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 spanning 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 $G$ has a perfect matching $M$ such that some two non-incident edges of $G-M$ do not lie together in a perfect matching of $G-M$. (Comment: Since $G-M$ is regular, this shows a sense in which part (a) is sharp.)
• Corollary 3.1.13 proves the Marriage Theorem from Hall's Theorem. Prove the Marriage Theorem using the Konig-Egervary Theorem instead.
• (!) Let $G$ be a connected regular bipartite graph. Let $G'$ be obtained from $G$ by deleting one vertex from each partite set. Prove that $G'$ has a perfect matching.
• (Replacement for Exercise 3.1.23.) Stronger versions of Hall's Theorem. Let $G$ be a 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 covers $X$. (Hint: Use induction on $\C X$.)
  (b) If $d(x) \ge k$ for all $x$ in $X$, and $\C X = k$, then there are at least $k!$ matchings that cover $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 \gt 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)}$.
• (!) Prove that if $G$ is an $n$-vertex graph, then $\alpha'(G)\ge \min{\FL{n/2},\delta(G)}$.
• Let $i(H)$ denote the number of isolated vertices in a graph $H$; note that $i(H)\le o(H)$. For $t\ge2$, prove that a graph $G$ has a factor whose components are nontrivial stars with at most $t$ edges if and only if $i(G-S)\le|S|$ for all $S\esub V(G)$. (Comment: The condition does not reduce to the condition for a $1$-factor when $t=1$.) (Amahashi--Kano [1982])
• 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_1,\ldots,A_m$ such that $A_1\esub\cdots\esub A_m$.) (Galvin)
• Let $G$ be an $X,Y$-bigraph with $|X|\ge|Y|$ and no isolated vertices. Prove that $G$ contains a matching $M$ whose vertex set is $S\cup N(S)$ for some $S\subseteq X$. (Borodin-Kostochka-Woodall [1997])
• 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_1,\ldots,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, JCT 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 will be added to the main text as an application of Hall's Theorem. It gives another proof for a supplementary problem for Section 1.4.) (Hakimi [1965])
• Prove that in a bipartite graph, a vertex belongs to some smallest vertex cover if and only if it is covered by every maximum matching.
• 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.
• (!) Determine the largest number $b$ such that every maximal matching in every $3$-regular graph has size at least $b|V(G)|$.
• Let $G$ be an $X,Y$-bigraph with maximum degree $D$ that does not have $(m+1)K_2$ as an induced subgraph. Prove that $e(G) \le mD^2$. (Faudree-Gyárfás-Schelp-Tuza [1989])
• (!) Let $G$ be an $n$-vertex regular graph with positive vertex degree. Prove that $\alpha(G)\le n/2$, with equality only if $G$ is bipartite.
• 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 set 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 $G$ be an $n$-vertex graph with $m$ edges. Prove that $\beta(G)\le n/2+m/6$, with equality only when every component of $G$ is $K_3$ or $K_4$. (Hint: Consider cases depending on $\Delta(G)$.) Henning--Yeo [2013])
• Let $v_1,\ldots,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=\CL{\sum 1/(1+d_G(v_i)}$. Prove that the last $k$ vertices in the ordering form an independent set. (Caro--Tuza [1991])
• Let $G$ be an $n$-vertex graph not having $K_{1,3}$ as an induced subgraph. Prove that $\alpha (G)\le (2n)/(\delta (G)+2)$.
• For a graph $F$ and $n\ge|V(F)|$, an $n$-vertex 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ászonyi--Tuza [1996] obtained a bound linear in $n$; Füredi gave this more precise result.)
• 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 nontrivial 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 $2r+1$ vertices in which every set of at most $r$ vertices has a common neighbor. Prove that some vertex in $G$ is adjacent to all the others.
• Let $G$ be a graph with girth $l$. Prove that if $\delta(G)\ge 2$ and $l \ge5$, then $\gamma(G)\le\CL{(n-\FL{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 $\CL{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$. Thus $V(G_m)={0,\ldots,m}\times {0,\ldots,m}$, with $(i,j)$ and $(i',j')$ adjacent if and only if they differ by 1 in one coordinate. Determine $\lim_{m\to\infty}\gamma(G_m)/\C{V(G_m)}$.
  b) Let $H_m$ be the triangular grid with side-length $m$. Thus $V(H_m)={(i,j,k)\in\NN_0^3\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} \gamma(H_m)/\C{V(H_m)}$.
  c) Obtain a similar result for the hexagonal grid (all bounded faces are hexagons).
• Let $G$ be an $n$-vertex graph in which, for every vertex $v$, there are at least $c$ vertices within distance $d$ of $v$. Prove that there is a set $S$ of at most $n/c$ vertices such that every vertex in $G$ is within distance $2d$ of some vertex in $S$.
• A $p$-dominating set is a vertex subset $S$ such that every vertex outside $S$ has at least $p$ neighbors in $S$. Let $\gamma_p(G)$ denote the minimum size of such a set in a graph $G$.
  a) Prove that if $\Delta(G)\ge p\ge 2$, then $\gamma_p(G)\ge \gamma(G)+p-2$. (Fink--Jacobson [1985])
  b) Prove that if $\gamma_2(G)=\gamma(G)$, then $\delta(G)\ge2$ and every smallest $2$-dominating set is an independent set. (Hansberg--Volkmann [2007])
• For a vertex subset $T$ in a graph $G$, a $T$-join is a spanning subgraph of $G$ in which the degree of every vertex in $T$ is odd and the degree of every vertex outside $T$ is even. Prove that if $T$ is contained in the vertex set of one component of $G$, then $G$ has a $T$-join if and only if $|T|$ is even.
• Let $G$ be an $X,Y$-bigraph (without multi-edges) having a matching that covers $X$. Prove that if $d(y)\ge k$ for all $y\in Y$, then $G$ has at least $k!$ matchings covering $X$. For each $k$, construct an infinite family of examples where there are only $k!$ such matchings. (Kostochka)
• Let $G$ be an $X,Y$-bigraph with $|X|=|Y|$. Prove that $G-\{x,y\}$ has a perfect matching whenever $x\in X$ and $y\in Y$ if and only if $|N(S)|\gt|S|$ for every nonempty proper subset $S$ of $X$. (Lovász-Plummer [1986])
• Given a graph $G$, let $G'$ denote the graph with vertex set $V(G)$ whose edges are the pairs of vertices that have a common neighbor in $G$. Prove $|E(G')|\ge |E(G)|-\FL{n/2}$, and show that this is sharp. (Hint: Consider a maximal matching $M$ and show that $G'$ has at least $|E(G)|-|M|$ edges.) (Füredi [1992])

Section 3.2

• Let $G$ be an $X,Y$-bigraph with $|X|\le|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.)
• Prove that every tree has a maximum matching that covers every non-leaf vertex plus at least one leaf. (Lih-Lin-Tong [2006])

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 $e$ be a cut-edge in a connected graph $G$ having a perfect matching $M$. Prove that $e\in M$ if and only if $G-e$ consists of two components with odd order. Conclude that if every vertex of $G$ has odd degree, then every perfect matching in $G$ contains all cut-edges of $G$.
• 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 connected 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 and $b$ leaf blocks.
  a) Determine the maximum possible value of $b$ in terms of $n$.
  b) Prove that $\alpha'(G)\ge n/2-b/3$. (Hint: Use the Berge--Tutte Formula.)
  c) Determine the minimum possible value of $\alpha'(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 connected 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])
• (-) Given a graph $G$, prove that a set $A\subseteq V(G)$ intersects every minimal dominating set in $G$ if and only if $A$ contains the closed neighborhood of some vertex of $G$.
• Prove that every nontrivial connected graph has a smallest dominating set $S$ in which every vertex has a neighbor that is not dominated by any other vertex of $S$.
• In a graph $G$, a vertex subset $D$ is {\it $k$-dependent} if $\Delta(G[D])\lt k$, and it is {\it $k$-dominating} if $\C{N(v)\cap D}\ge k$ for $v\in V(G)-D$. Let $f(D)=k\C D-\C{E(G[D]}$. Prove that every $k$-dependent set maximizing $f$ is $k$-dominating. (Comment: Proved in Favaron [1985], this implies the conjecture of Fink--Jacobson [1985] that some $k$-dominating set is no bigger than some $k$-dependent set.)

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-1$ is positive 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)
• (-) Prove that every regular graph of even degree has even edge-connectivity.
• (-) Let $M$ be a matching of size $r$ in $K_{r,s}$, where $r\le s$. Prove that $K_{r,s}-M$ is $(r-1)$-connected unless $(r,s)=(2,2)$.
• 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)\gt 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 and at least $4$, 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 edge-connectivity are equal, other than a complete graph. Let $F$ and $S$ be a smallest edge cut and smallest separating set, respectively. Prove that each vertex of $S$ is incident to exactly one edge of $F$. (Ramras)
• For integers $j$ and $k$ with $j$ even and $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 $\kappa(G)=\delta(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 $\kappa'(G)=\delta(G)$.)
  b) Construct an example to show that $\kappa(G)\lt \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$.
• (!) Given vertices $u$ and $v$ in a connected graph $G$, prove that there is a unique partition of $V(G)$ into sets $A$ and $B$ inducing connected subgraphs such that $u\in A$, $v\in B$, and every edge joining $A$ and $B$ is incident to $v$. (Bolian Liu [1985])
• 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\ge 6$, prove that the double-wheel $C_{m-2}\join 2K_1$ 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 connected 3-regular graph having no cut-edge. Prove that every two edges in $G$ lie on a common cycle.
• (-) 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 2-edge-connected graph. Prove that $G$ is 3-edge-connected if and only if for every edge $e$ in $G$, no other edge lies on every cycle containing $e$.
• (-) A thread in a graph is a path that is maximal subject to the condition that the internal vertices have degree 2. Prove or disprove: The last ear added in an ear decomposition of a 2-connected graph $G$ that is not a cycle can be any thread in $G$.
• (-) 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$.
• The integer simplex (or triangular grid) with dimension $d$ and side-length $m$ is the graph $T_m^d$ whose vertices are the nonnegative integer $(d+1)$-tuples summing to $m$, with two vertices adjacent when they differ by $1$ in two places and are equal in all other places. Determine $\kappa(T_m^d)$. (Ma)
• 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.)
• Determine the smallest $m$ such that every 2-connected graph with $n$ vertices has a 2-connected spanning subgraph with at most $m$ edges.
• 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])
• Let $v$ be a vertex in a $k$-connected graph $G$. Prove that the graph obtained from $G$ by subdividing every edge incident to $v$, adding edges to make the new vertices pairwise adjacent, and deleting $v$ is $k$-connected.
• 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 \ge 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.)
• A $k$-connected graph is minimally $k$-connected if deleting any edge reduces the connectivity below $k$. Halin [1969, 1971] proved that every minimally $k$-connected graph has a vertex of degree $k$. For all positive integers $k$ and $\ell$, construct a minimally $k$-connected graph having a vertex with distance at least $\ell$ from all vertices of degree $k$.

Section 4.3

• Use network flows to prove Hall's Theorem.
• Let $G$ be an $X,Y$-bigraph with $X=\{\VEC x1t\}$. Let $\VEC d1t$ be positive integers at most $k$. Prove that $G$ has a $k$-edge-colorable subgraph $H$ such that $d_H(x_i)=d_i$ for $i\in[t]$ if and only if $\sum_{v\in D}\min\{k,\C{N(v)\cap S}\}\ge \sum_{v\in S} d_i$ for all $S\esub X$. (Folkman--Fulkerson, Lebensold)

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$.
• Let $G$ be a $K_{1,t+1}$-free graph. Prove that $\chi (G)\ge 1+\Delta (G)/t$. For all $k,t\in\NN$, construct a $k$-chromatic graph for which equality holds in the bound. (Zaker [2011])
• 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)$.
• Consider the coloring algorithm that iteratively chooses a maximal independent set and gives it the next color. Show that this algorithm can perform very badly, using $n/2$ colors on an $n$-vertex graph with chromatic number 2.
• The integer simplex (or triangular grid) with dimension $d$ and side-length $m$ is the graph $T_m^d$ whose vertices are the nonnegative integer $(d+1)$-tuples summing to $m$, with two vertices adjacent when they differ by $1$ in two places and are equal in all other places. Determine $\chi(T_m^d)$.
• Let $G$ be a graph with $mn$ vertices that decomposes into $nK_m$ and $mK_n$. Prove that $G\cong K_m\cart K_n$. Construct infinitely many examples in which $F$ and $H$ are graphs with $m=|V(F)|$ and $n=|V(H)|$ and some graph $G$ with $mn$ vertices decomposes into $nF$ and $mH$ 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) \le 2\omega(G)-1$.
• Prove or disprove: the underlying graph of a digraph with maximum outdegree $d$ is $(2d+1)$-colorable.
• 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 every subgraph of $G$ has a vertex with degree at most $\sqrt{4k+1}$. (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])
• Given a spanning tree $T$ in a graph $G$, let $\chi(G;T)$ denote the least $k$ such that $G$ has a proper coloring using colors in $[k]$ such that vertices adjacent in $T$ have colors differing by at least $2$. The \df{backbone chromatic number} of $G$ is the minimum of $\chi(G;T)$ over all spanning trees $T$. Prove that every nonbipartite graph has backbone chromatic number at least $4$.
• A defining set for $k$-coloring a graph $G$ is a vertex subset having some coloring that extends to a proper $k$-coloring of $G$ in a unique way. Prove that the minimum size of a defining set for $3$-coloring the Petersen graph is $4$.
• 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 $\RR^3$ (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ász [1978] proved Kneser's conjecture that always $\chi(K(n,k))=n-2k+2$.)

Section 5.2

• Prove that every triangle-free graph is an induced 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$.)
• For $j\lt k\lt n-k$, determine the minimum size of an $n$-vertex $k$-chromatic graph with minimum degree at least $j$.
• 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_4$]
• Prove that 11 is the smallest number of vertices in a triangle-free 4-chromatic graph.
• Let $v$ be a vertex in a $k$-(color)-critical graph $G$. Prove that $G$ has an optimal coloring such that for all $u\in N[v]$, all colors appear on $N[u]$.
• For $k\in\NN$, prove or disprove: When the Hajós 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/2^r}-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_4$. 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

• 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.
• (-) Find graphs $G$ and $H$ such that $\XPOL{G\join H}k=\XPOL Gk\XPOL Hk$, or show that no such graphs exist.
• (-) Prove that the complement of an odd cycle with at least five vertices contains a chordless odd cycle.
• In terms of the chromatic polynomial of $G$, determine the chromatic polynomial of $G\join 2K_1$.
• 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-\omega(G)}$.
• 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$.
  b) Prove that the center of $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.)
• Let $S$ be a maximal independent set and $Q$ be a maximal clique in a $P_4$-free graph $G$. Prove that $S$ and $Q$ have a common vertex.

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 simple planar graph has a triangle.
• (-) Every outerplanar graph is 2-degenerate. Find a 2-degenerate graph that is not outerplanar.
• (-) 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 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 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_6$ be the number of faces of length 6. For $k\ge0$, construct a fullerene with $f_6=5k$ and a fullerene with $f_6=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.
• Determine all isomorphism classes of simple triangulations having exactly $k+2$ vertices, with $k$ vertices of degree 4 and two vertices of degree $k$
• Construct two nonisomorpic simple 9-vertex triangulations having the same degree list.
• (!) 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_1,\ldots,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átal, 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_6$ decomposes into two outerplanar graphs but $K_7$ does not. (Hint: Prove that the complement of any 7-vertex maximal outerplanar graph is not outerplanar.)
• (+) Prove that there is no 5-regular simple 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 rhombicosidodecahedron 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 rhombicosidodecahedron.
• Let $G$ be a bipartite planar graph such that for any distinct $u,v\in V(G)$, the number of shortest $u,v$-paths in $G$ is odd. Prove that $G$ is a tree.
• (!) 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.)
• Use the Four Color Theorem to prove that every 3-regular graph with crossing number 1 is 3-edge-colorable
• 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])
• Let $H$ be an $n$-vertex $k$-regular graph that decomposes into $k$ perfect matchings.
  (a) Prove that if $K_n$ decomposes into $t$ copies of $H$ plus a leftover perfect matching, then the multigraph $K_n^{(k)}$ having $k$ copies of each vertex pair as edges decomposes into $kt+1$ copies of $H$.
  (b) Apply part (a) to the octahedron (Adams-Billington-Rodger [1994]), the cube (Adams-Bryant-ElZanati [1995]), and the icosahedron (Rosenfeld [2022]).

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_5$.
• (-) 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_6$ by deleting a perfect matching.
  The graph obtained from $K_6$ by deleting a matching $M$ with two edges and subdividing the edge joining the two vertices not incident to $M$.
• Prove or disprove: Every bipartite graph with minimum degree at least 4 contains $K_{3,3}$ as a subgraph.
• Prove or disprove: The union of any two paths is a planar graph.
• Let $G$ be the graph obtained from the 3-dimensional cube $Q_3$ 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.
• For $n\ge5$, prove that the square of $C_n$ is planar if and only if $n$ is even. Prove necessity of the condition in two ways:
  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.
• {\it Planarity of cartesian products.}
  a) Use the characterization of outerplanar graphs to prove that $G\cart K_2$ is planar if and only if $G$ is outerplanar.
  b) For connected graphs $G_1$ and $G_2$ with at least three vertices, prove that $G_1\cart G_2$ is planar if and only if both are paths or one is a cycle and the other is a path. (Behzad--Mahmoodian [1969])
• Let $H$ be the icosahedron.
  a) Let $H'$ be the $12$-vertex graph on $V(H)$ in which vertices are adjacent if the distance between them in $H$ is $2$. Prove that $H'$ is isomorphic to $H$.
  b) Prove that there are $11$ copies of $H$ in $K_{12}$ such that each edge of $K_{12}$ appears in exactly five of them.

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_3+2n_4+n_5 \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 Algor--Alon [1989] that every planar graph decomposes into five forests whose components are stars. (Hakimi-Mitchem-Schmeichel)
• For $n\in \NN$, construct an $n$-vertex triangulation having more than $2^n$ proper colorings from [4] and another having only 24 such colorings.
• Consider $j,k\in\NN$ with $0\le j\lt k$, and let $G$ be a graph with minimum degree $k$. Use discharging to determine the largest $\rho$ such that if the average degree in $G$ is less than $k+\rho$, then $G$ must have a vertex of degree $k$ with more than $j$ neighbors of degree $k$.
• Let $f$ be a proper vertex coloring of an $n$-vertex triangulation using the colors {$a,b,c,d$}. Let $M$ be the number of edges joining colors $a$ and $b$ plus the number of edges joining colors $c$ and $d$. Determine $M$. (X. Lv)
• (!) Prove that $7\le \nu(K_7)\le 9$.
• (!) A planarity criterion.
  a) Prove that in every drawing of $K_5$ 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_6$ on the projective plane, and show that the dual is the Petersen graph.
• (*) Embed the Grötzsch 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])
• (-) For a graph $G$, prove that $\chi '(G)\ge \sum 1/m(e)$, where the sum is over all edges and $m(e)$ is the maximum size of a matching containing edge $e$.
• (!) (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.
• (!) Chetwynd-Hilton [1986] proved that simple graphs with at most two vertices of maximum degree are Class 1. Use the join of $K_3$ and the complement of any matching to prove that this is sharp.
• (Replacing 7.1.28) Prove that the Petersen graph has no overfull subgraph, but that both the Petersen graph and the graph obtained from it by deleting one edge are Class 2.
• The integer simplex (or triangular grid) with dimension $d$ and side-length $m$ is the graph $T_m^d$ whose vertices are the nonnegative integer $(d+1)$-tuples summing to $m$, with two vertices adjacent when they differ by $1$ in two places and are equal in all other places. Determine $\chi'(T_m^d)$.
• 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. For $m\ge2$, prove that $G$ is a simple graph with fewest vertices among those with maximum degree $2m-1$ and edge-chromatic number $2m$.
• (+) Let $G$ be a 1-factorable graph with even degree. 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)\gt\Delta(G)$, then $G$ has a minimal subgraph $G'$ such that $\chi'(G')\gt\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\ouml 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$.
• (!) Let $\hat P$ denote the Petersen graph.
  (a) Prove that $\hat P$ has exactly 12 perfect matchings.
  (b) Prove that any two perfect matchings in $\hat P$ share exactly one edge.
  (c) Prove that $E(\hat P)$ cannot be covered by four perfect matchings.
  (Comment: Berge conjectured that the edges of any $2$-edge-connected $3$-regular graph can be covered using at most five perfect matchings. The Petersen graph shows that this conjecture is sharp. Fulkerson [1971] conjectured that every $2$-edge-connected $3$-regular graph has six (not necessarily distinct) perfect matchings such that every edge appears in exactly two of them. Trivially, Fulkerson's Conjecture implies Berge's Conjecture. Mazzuoccolo [2010] used the result of this exercise to show that Berge's Conjecture implies Fulkerson's Conjecture.)

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.
• (-) Prove that the square of a cycle is Hamiltonian-connected.
• 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)
• (!) An $n$-vertex graph is pancyclic if it has cycles of all lengths from 3 to $n$. Determine which complete multipartite graphs are pancyclic.
• (!) Let $G$ be an $n$-vertex Hamiltonian graph. Prove that $G\cart K_{1,m}$ is Hamiltonian if and only if $n\ge m$. (Comment: Lai-Li-Lu [2010+] proved that the statement remains true with any tree of maximum degree $m$ in place of $K_{1,m}$.)
• (!) 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$.
• Let $v$ be a vertex of degree $3$ in a graph $G$. Let $G'$ be the graph obtained by replacing $v$ with a triangle joined to $N_G(v)$ by a matching. Prove that $G$ and $G'$ have the same number of spanning cycles.
• Prove that every 2-connected, claw-free, paw-free graph is Hamiltonian (Goodman-Hedetniemi [1974])
• Prove that every $k$-regular $k$-edge-connected graph is 1-tough. (Comment: Hence every such graph also has a 1-factor.)
• Determine the maximum number of edges in a subgraph of $K_{n,n}$ having no cycle of length $2n$. (Entringer--Schmeichel [1988])
• Prove that the $k$-dimensional hypercube $Q_k$ has a spanning path whose endpoints are complementary if and only if $k$ is odd. Prove that it has a spanning path with endpoints differing in all but one position if and only if $k$ is even. (Hint: Prove both statements simultaneously.)
• (!) 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])
• Let $G$ be an $n$-vertex graph having no induced subgraph that is a star with $t$ edges, where $t\ge2$. Prove that if $\kappa(G)\ge \sqrt{(t-1)n}$, then $G$ is Hamiltonian.
• 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_1$ 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 \ge 2$, the hypercube $Q_k$ is a Hamiltonian bipartite graph. For $k \ge 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)
• Let $G$ be an $n$-vertex graph such that $d(x)+d(y)\ge n-1$ whenever $xy\notin E(G)$. Prove that $G$ has a perfect matching and that this may fail when $n-1$ is changed to $n-2$. (Hint: Apply Ore's Theorem.)
• Construct a 3-connected 4-regular graph that is not Hamiltonian. (Hint: Modify the Petersen graph.)
• Prove that there is a 3-connected 3-regular non-Hamiltonian graph with $n$ vertices whenever $n$ is even and at least 10.
• 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,\ldots,n-1$. (Jiang-West)
• (!) For even $n$, prove that if $G$ has vertex degrees $\VEC d1n$ in nondecreasing order, and $d_i\ge i+t-1$ for $1\le i\le n/2-1$, then $G$ has $t$ edge-disjoint perfect matchings. (Hint: Apply Chvátal's Theorem to a modified graph.)
• (+) Prove that if a graph satisfies Chvátal'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.
• (+) Let $f(l)$ be the maximum $t$ such that every $2$-connected graph containing a path of length $l$ contains a cycle of length at least $t$. Prove $f(l)\ge\sqrt{2l}$ for all $l$, and prove $f(l)\le 2\sqrt l$ for infinitely many $l$. (Comment: Dirac [1952] proved this and $f(l)\ge2\sqrt l$ for all $l$.)
• 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_4$. 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)
• Let $G$ be a $3$-regular graph. Prove that $G$ has exactly three spanning cycles if and only if $E(G)$ has exactly one partition into three perfect matchings.

Section 8.1

• (-) Prove that $\omega(G)\ge 1+\Delta(G)/2$ for every claw-free perfect graph $G$.
• 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 graph $G$ with distinct labels on the edges contains an increasing trail whose length is at least the average vertex degree in $G$. (Winkler)
• Prove that every 2-coloring of the edges of $K_5$ that has no monochromatic triangle consists of two monochromatic 5-cycles.
• Let $n=R(k,l)$. Prove that the edges of the graph obtained from $K_n$ by deleting one edge can be 2-colored with no red $K_k$ or blue $K_l$. (Chvatal [1974])
• Let $T$ be a tree with $m$ vertices. Prove that there is only one 2-coloring of $E(K_{(m-1)(n-1)})$ (up to isomorphism) that has no red $T$ or blue $K_n$. Conclude that if $G$ is formed from $K_{(m-1)(n-1)}$ by adding one vertex adjacent to $s$ vertices of the clique, then all red/blue colorings of $G$ have a red $T$ or a blue $K_n$ if and only if $s\gt (m-1)(n-2)$ (Hook-Isaak [2010+])
• Show that $K_{5,5}$ has a 3-edge-coloring with no monochromatic $P_5$
• Prove that $R(C_5,K_4)=13$ (Comment: Erdos-Rousseau-Schelp (see Faudree--Schelp [1978] (LMS 642)) conjectured that $R(C_m,K_n)=(m-1)(n-1)+1$ when $m\ge n$ and $(m,n)\ne (3,3)$. This was proved for $n=4$ in Yang-Huang-Zhang [1999], for $n=5$ in Bollobas-Jayawardene-Yang-Huang-Rousseau-Zhang [2000], for $n=6$ in Schiermeyer [2003], and for $m\ge 4n+2$ in Nikiforov [2005].)
• 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) \le 4^k$.
• Let $G$ be a graph in which every induced subgraph of order $2k$ has independence number $k$. Prove that $n(G) \lt R(3,k+1)+3$. (Comment: This places an upper bound of about $k^2/\log k$ on $n(G)$, but the best bound is linear.) (Andreas Brieden)
• (!) 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_3,\ZZ_3)=11$.
• Prove that the bandwidth of the cartesian product of two $n$-cycles is at least $2n-1$, with equality for $n\in\{3,4\}$. (Comment: In fact, equality holds for all $n$, which is not too messy for odd $n$.) (Li-Tao-Shen [1981]
• 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 number of vertices outside $S$ having neighbors in $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.)
• The Haj\'os Conjecture states that every $n$-vertex even graph decomposes into $n/2$ cycles. Prove that if the Haj\'os Conjecture is true, then every $n$-vertex graph decomposes into $3n/2$ cycles and edges. (Pyber [1984, 1992], Dean [1987])

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_1,\ldots,l_k)$ with branch vertices $u$ and $v$ is the union of $k$ pairwise internally-disjoint $u,v$-paths with lengths $l_1,\ldots,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_4$ 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.
• Determine $\chi_l(K_{3,3,1})$.
• Prove that $K_{2r+1}$ decomposes into $r$ paths and a matching.

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_1,\ldots,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.
• (!) Given that recognition of Hamiltonian graphs is NP-complete, show that recognition of Hamiltonian digraphs is NP-complete. (Karp [1972])

More to Come!