Introduction to Graph Theory  Second Edition
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.
Note: Notation on this page is now in MathJax. Rightclick 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
$
\def\nul{\emptyset}\def\NN{{\bf N}}\def\ZZ{{\bf Z}}\def\RR{{\bf R}}
\def\FL#1{\lfloor{#1}\rfloor}\def\CL#1{\lceil{#1}\rceil}
\def\C#1{\left{#1}\right} \def\esub{\subseteq}
\def\FR#1#2{{{#1}\over{#2}}} \def\st{\colon\,} \def\join{\vee}
\def\Sb{\overline{S}} \def\cart{\square} \def\CH#1#2{{#1\choose #2}}
\def\XPOL#1#2{\chi_{#1}(#2)}
\def\VEC#1#2#3{#1_{#2},\ldots,#1_{#3}}
$
Supplementary Problems by Section
Section 1.1
 () Count the isomorphism classes of subgraphs of the kite (now
diamond).
 () 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_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 4regular 9vertex 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=10$ than for $n=8$.
 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
 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^22k+2$
vertices. (Comment: There is such a graph with exactly $2k^22k+2$
vertices when $k1$ 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 4tuples, with two 4tuples 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 5cycle
in the Petersen graph is a 5cycle. Prove that every 6cycle contains
three edges from one of these 5cycles and one edge from the other.
 Let $e$ and $e'$ be nonincident 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.
 Determine the number of maximumsized 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.
 (+) 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 2regular and has no 4cycle.
b) Determine the conditions under which $A$ is the incidence matrix
of $G$ itself.
 The Möbius ladder $M_k$ is the 3regular 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 edgetransitive.
 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: Every Eulerian graph has no
cutedge.
 () 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$.
(CartwrightHarary [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 $GE(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 5cycle) cannot be expressed
as the union of two cycles.
 By Exercise 1.1.31, there is a selfcomplementary graph with $n$
vertices if and only if $n$ or $n1$ is divisible by 4. Prove that
for each such $n$ there is a selfcomplementary graph having a cutvertex.
(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 $\sumu_iv_i=r$.
a) Prove that $G$ is disconnected if $r$ is even.
b) Prove that $G$ is bipartite if $r$ is odd.
(FurediKang [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 $(g2)(k1)+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$. (HararyKovacs [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 cutedge). For $n\ge 3$, prove that the minimum of
$E(G)+c(G)$ among $n$vertex connected graphs is
$n+\lceil 2(n1)^{1/2}\rceil $. (ButlerMao [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.) (CaroRoditty
[2004])
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 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(n1)/k$ edges.
 () Prove that the complement of an odd cycle with at least five vertices
contains a chordless odd cycle.
 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.
 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 4cycles in $K_{m,n}$.
 Determine the number of isomorphism classes of 3regular simple
graphs with eight vertices.
 Determine all the isomorphism classes of selfcomplementary graphs with
five vertices.
 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)
 For $n\ge2k$, determine the minimum number of distinct cycle lengths
in an $n$vertex graph with minimum degree $k$.
 For $n\ge 5$, prove that there is only one isomorphism class of
$n$vertex graphs having two vertices of degree 1, one vertex of degree
$n5$, and $n3$ vertices of degree $n3$.
 An allodd 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 allodd graphs.
 Prove that if $\delta (G)\ge 3$, then some cycle in $G$ has a
chord. (Czipzer)
 (!) 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$.
 Let $G$ be an $n$vertex graph with $\delta(G)\ge n/4$ and no cutedge.
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.
 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)$.
 Determine all trianglefree nonbipartite graphs $G$ in which the degrees of
any two vertices sum to at least $V(G)1$.
 Determine whether every 3regular trianglefree connected simple graph with
eight vertices is isomorphic to the 3dimensional cube
$Q_3$.
 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.
 Determine whether there is a 4regular graph with nine vertices that is
not isomorphic to its complement.
 Prove that a list of $n$ positive numbers with largest element $r$ and even
sum is graphic if $n\ge r^2$. (Sivaraman [2013]; see ZverovichZverovich [1992]
for the exact threshold length.)
 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. (FulkersonHoffmanMcAndrew [1965])
 (+) For $k\in\NN$, let $D(k)$ denote a list of $4k$ integers
consisting of $2k$ copies of $3k1$ and $2k$ copies of $k$.
a) Prove that if $k\le3$, then every graph with degree list $D(k)$ is
selfcomplementary. (Hint: Describe all isomorphism classes of 3regular
bipartite graphs with 12 vertices.) (based on a communication from Josh
Brownfield)
b) Prove that if $k\ge4$, then some graph with degree list $D(k)$ is not
selfcomplementary.
 (+) 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 degrees are $j$ and $kj$,
respectively. Prove that $j=k/2$. For $j=k/2$, find a construction
(by induction on $k$) that works. (T. Biyikoglu)
 An $n$vertex simple graph has $n1$ 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
cutedge 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$.
 (+) Prove that an even graph with $n$ vertices and $m$ edges
decomposes into at most $n\log m$ cycles.
 Prove that a graph whose vertexdeleted subgraphs are all trees is
reconstructible.
 (!) Let $n$ and $k$ be positive integers such that $n$ is divisible by
$k1$. Determine the minimum number of edges in an $n$vertex graph such that
every induced subgraph with $k$ vertices is connected. (Comment: The ideas
generalize when the divisibility condition is dropped to obtain upper and lower
bounds that differ by less than $k^2/8$.)
 (!) Determine the minimum number of edges in a maximal trianglefree
$n$vertex simple graph.
 (!) Let $H$ be a simple graph with $n$ vertices. Prove that
if $n \gt k$ and $e(H) \gt (k1)(nk/2)$, then $H$ contains a
subgraph with minimum degree at least $k$. (Bollobás [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)\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), 170176])
 Given an $X,Y$bigraph $G$ and edges
$x_1y_1$ and
$x_2y_2$ with
$x_1,x_2\in X$ and
$y_1,y_2\in Y$, say that a bridging operation
deletes $x_1y_1$ and $x_2y_2$
and adds two new vertices $x_3$ and
$y_3$ with
$N(x_3)={y_1,y_2,y_3}$ and
$N(y_3)={x_1,x_2,x_3}$.
Prove that every 3regular 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 3regular 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.)
 (+) The notion of selfcomplementary graphs can be generalized by saying
that $n$vertex graphs $G_1$ and $G_2$ pack if $K_n$ contains
edgedisjoint copies of $G_1$ and $G_2$. Prove that $G_1$ and $G_2$ pack if
$2\Delta(G_1)\Delta(G_2) \lt n$. (SauerSpencer [1978])
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.) (Tarsi [1981])
 (!) Let $(a_1\ldots,a_n)$ be nonnegative integers with even sum. Prove
that if there is a simple digraph with vertex set $\{v_1,\ldots,v_n\}$ such
that $v_i$ has indegree and outdegree $a_i$ for $1\le i\le n$, then
$(a_1,\ldots,a_n)$ is a graphic list. (Chen [1980])
 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 $n1$ 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 $G$ be an oriented graph with at least three vertices. Prove that
edges can be added to extend $G$ to a strong oriented graph if and only if
$V(G)$ contains no nonempty proper subset $S$ such that $xy\in E(G)$ for all
$x\in S$ and $y\in\overline{S}$.
 Let $G$ be a graph with vertex degrees $d_1,...,d_n$. Prove that the
number of acyclic orientations of $G$ is at most $\prod (d_i+1)$.
 (!) 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 3cycles in $T$ is
${n\choose 3}\sum_{v\in V(T)}{d^+(v)\choose 2}$. (KendallSmith [1940])
(Kendall, J.B. and Smith, B.B., 1940. On the method of paired comparisons.
Biometrika 31, pp. 324345)
b) Given that $n$ is odd, determine the maximum possible number of
3cycles 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 $Gv$ 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 $n1$ 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$ edgedisjoint spanning trees,
and let $e_1,\ldots,e_k $ be distinct edges in $G$.
Prove that $G$ has edgedisjoint 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)
 Let $T$ and $T'$ be trees with $n$ vertices.
For $1\le j \le n1$, 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_jb_j)]= 0$.
 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 pairwiseintersecting 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 vertexdeleted subgraphs that are acyclic. (Myrvold [1990])
 (!) Determine the maximum number of cutedges in a 3regular graph with
$n$ vertices. (OWest [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 distancesum (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.
 Let $G$ be an $n$vertex circulant degree with diameter at least 3.
Prove that $G$ has degree less than $n/2$. (Buratti) (Comment: The result
holds more generally for Cayley graphs.
 Prove that there is a 16vertex 5regular graph with diameter 2.
 Prove that there is a 16vertex tree with maximum degree 4 and eight
vertices in each partite set that is not a
subgraph of the 4dimensional 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) > 2$,
then $d(x,y)\le l+2d(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^{nk1}$. 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]^{nk1}\times [k]$.
 Show that a graceful graph may have a nongraceful 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 minimumweight spanning tree.
 () Prove or disprove: In a weighted graph the edges of smallest weight
appear in every minimumweight 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
8cycle 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 trianglefree 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,1matrix 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,1matrix equals the minimum number of
lines that together contain all the 1s.
 (!) 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 $r1$ 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/(2k1)$. Prove that equality is
achievable when $2k1$ 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 nonincident edges of $GM$
do not lie together in a perfect matching of $GM$. (Comment: Since $GM$
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 KonigEgervary 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], HalmosVaughan [1950])
 Construct a bipartite graph with no cutedge and no cutvertex 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.
(KezdySnevily see CameronWanless [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(GS)\leS$ for all $S\esub V(G)$. (Comment: The condition does not reduce
to the condition for a $1$factor when $t=1$.) (AmahashiKano [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\geY$ and no isolated vertices.
Prove that $G$ contains a matching $M$ whose vertex set is $S\cup N(S)$
for some $S\subseteq X$. (BorodinKostochkaWoodall [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=d1$ 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), 8184)
 (!) 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])
 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.
 Define the $m$deficiency $\delta_m(v)$ and
$m$excess $\epsilon_m(v)$ of a vertex $v$
by $\delta_m(v)$=max{$0,md(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\in X}\delta_m(x)+\sum_{y\in Y}\epsilon_m(y) \lt 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.
 (!) Determine the largest number $b$ such that every maximal matching in
every $3$regular graph has size at least $bV(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$. (FaudreeGyárfásSchelpTuza [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 cutedge 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)$.)
HenningYeo [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. (CT [1991])
 For a graph $F$ and $n\geV(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ászonyiTuza [1996] obtained a
bound linear in $n$; Füredi 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\gt k$, the result is a 3regular graph. The Petersen graph is
$P(5,2)$.
a) Prove that $\alpha(P(3k,k))=(5k/2)1$.
b) Prove that $\alpha(P(m,k))\ge \FR k{k+1}m$ when $m$ is divisible by $k+1$.
c) Prove that $\alpha(P(m,2))\ge 4m/5$ when $m$ is divisible by 5.
(+) d) Prove that $\alpha(P(m,2)\le 4m/5$. (Cranston)
 ()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$.
 () 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 $3m2$. 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}$. (BrighamDutton [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)$.
(BrighamDutton [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 coZelinka [1993])

Domination in planar grids.
a) Let $G_m$ be the square grid with sidelength $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 sidelength $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)+p2$.
(FinkJacobson [1985])
b) Prove that if $\gamma_2(G)=\gamma(G)$, then $\delta(G)\ge2$ and every
smallest $2$dominating set is an independent set.
(HansbergVolkmann [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\leY$. Prove that
$G$ has a maximal path with an endpoint in $Y$. (Comment: This
generalizes Exercise 2.1.29.) (KundgenRamamurthi 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 nonleaf
vertex plus at least one leaf. (LihLinTong [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 cutedge in a connected graph $G$ having a perfect matching
$M$. Prove that $e\in M$ if and only if $Ge$ 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 cutedges 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
$(k6)/2$ vertices have degree $k$ and the rest have degree
$k1$.
 Let $G$ be a simple graph with $\alpha'(G)=m$. Prove that
$G$ has at most $m(m1)$ 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 $GS$.
Conclude that every $K_{1,3}$free connected graph of even order has a
1factor.
 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/2b/3$. (Hint: Use the BergeTutte Formula.)
c) Determine the minimum possible value of $\alpha'(G)$.
(Comment: See Biedl et al.~[2004] for $3$regular graphs HenningYeo
[2007] generalized to regular graphs of higher degree.)
 Let $G$ be a graph with $2m$ vertices that has exactly one
1factor. 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 2factor in this graph is a spanning cycle.
 Let $G$ be a regular graph of degree $2r1$. 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 5cycles.
 Prove that every connected vertextransitive graph of even order has a
1factor.
 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 $(k1)$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}sSachs [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 1factor. (Hint: In proving that
$o(GS)\le \C S$ for all $S$, consider the expansion properties of
the set $T$ consisting of the vertices in all the odd components of
$GS$ except one.) (Anderson [1973])
 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 FinkJacobson [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 $nk1$ is positive and even, show that the
list consisting of $k1$ copies of $n1$ and $nk+1$ copies of $k$ is graphic
but has no $k$connected realization. (F. Jao)
 () Prove that every regular graph of even degree has even
edgeconnectivity.
 () Let $M$ be a matching of size $r$ in $K_{r,s}$, where $r\le s$. Prove
that $K_{r,s}M$ is $(r1)$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 3connected. Prove
that it is 3connected by using the Expansion Lemma and vertex splits.
 (!) Let $G$ be an $n$vertex graph with minimum degree $n3$.
Prove that if the complement of $G$ contains no 4cycle, then
$\kappa(G)=n3$.
 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, 7579.
 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 edgeconnectivity 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. (PlesnikZnam [1989])
 Girth, diameter, and connectivity.
a) Prove that $\kappa(G)=\delta(G)$ when $G$ is a graph with girth 5
and diameter 2. (Comment: SoneokaNakadaImasePeyrat [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
4vertex set $S$ such that $GS=2K_{3,3}$.)
 Prove that a vertex $v$ in a graph $G$ is a cutvertex 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 edgeconnectivity $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 doublewheel $C_{m2}\join 2K_1$ is
4connected and has cyclic edgeconnectivity $m$. (Plummer [1972])
 Prove that a graph has no induced subgraph with three leaf blocks
if and only if it is clawfree and netfree.
 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 3regular graph having no cutedge. Prove
that every two edges in $G$ lie on a common cycle.
 () Let $G$ be a 2connected 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 2edgeconnected graph. Prove that $G$ is
3edgeconnected 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 2connected graph $G$ that is
not a cycle can be any thread in $G$.
 () Let $G$ be a $k$edgeconnected 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$edgeconnected.
 Let $a$ and $b$ be nonadjacent vertices in a 2connected graph
$G$. Prove that if $Gab$ is connected, then $b$ lies on
a cycle in $Ga$.
 The integer simplex (or triangular grid) with dimension $d$
and sidelength $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 2connected 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 2connected graph with
$n$ vertices has a 2connected spanning subgraph with at most $m$
edges.
 Let $r$ be a vertex in a 2connected 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.) (ItaiRodeh [1984])
 Let $G$ be a 2connected 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
2connected. Let $f(G)$ be the minimum number of edges that must be
added to change $G$ into a 2connected 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 2connected
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 2connected graph, then
$G$ contains a cycle $C$ such that $GV(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 trianglefree 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. (SavageZhang [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 internallydisjoint
$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.)
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$edgecolorable
subgraph $H$ such that $d_H(x_i)=d_i$ for $i\in[t]$ if and only if
$\SM vD\min\{k,\C{N(v)\cap S}\}\ge \SM vS d_i$ for all $S\esub X$.
(FolkmanFulkerson, 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 3set) has an optimal coloring in which each color is used
twice. Prove that this coloring cannot be produced by the greedy coloring
algorithm. (FonDerFlaass)
 Construct a graph with nine vertices having an optimal coloring that cannot
arise via greedy coloring. (FonDerFlaass)
 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 sidelength $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.) (JiangWest)
 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
2colorable.) (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 ErdosSzekeres 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 n2k+2$ by covering the
vertices with $n2k+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))=n2k+2$.)
Section 5.2
 Prove that every trianglefree graph is an induced subgraph of a regular
trianglefree graph with the same chromatic number. (Comment: Thus for every
$k$ there is a regular trianglefree graph with chromatic number $k$.)
 For $j\lt k\lt nk$, 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 4critical, thereby showing that a
$k$critical graph need not be ($k1$)connected. [graph is
7vertex application of Hajos construction to two copies of
$K_4$]
 Prove that 11 is the smallest number of vertices in a trianglefree
4chromatic 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^{11/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), 217225, although the idea is like
that of Lemma 5.2.15)
 Replacement for Exercise 5.2.41 For $m=k(k+1)/21$, prove that
$K_{m,m}$ contains no $K_{2k}$subdivision.
 Let $G$ be a 2connected 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
 () Find graphs $G$ and $H$ such that $\XPOL{G\join H}k=\XPOL Gk\XPOL Hk$,
or show that no such graphs exist.
 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 $Ge$ 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$ (LaskarShier [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.)
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 cutedge in a plane graph $G$.
Prove that $e$ appears twice in the boundary of a single face.
 Construct a simple 4regular planar graph having an odd number of
vertices.
 () Let $G$ be a connected plane graph. Prove that the
edgeconnectivity of $G^*$ equals the girth of $G$.
 () Prove or disprove: Every 4regular simple planar graph has a
triangle.
 () Every outerplanar graph is 2degenerate. Find a 2degenerate 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 3connected. 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 2connected 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 2edgeconnected 3regular plane graph is 3connected 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 3regular 3connected plane graph in which 12 faces are 5cycles
and all other faces are 6cycles 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, 744751) showed that there exist fullerenes with every
number of 6cycle 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 9vertex 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 $ij\le3$.
Determine whether $G$ is a planar graph.
 Determine all $n$ such that there exists a 4regular simple planar
graph with $n$ vertices. (V. Chvátal, Planarity of graphs with given
degrees of vertices, Nieuw. Arch. Wisk. 17 (1969), 4760, and
A. B. Owens, On the planarity of regular incidence sequences,
J. Combinatorial Theory Ser. B 11 (1971), 201212.
 (!) Prove that $K_6$ decomposes into two outerplanar graphs
but $K_7$ does not. (Hint: Prove that the complement of any
7vertex maximal outerplanar graph is not outerplanar.)
 (+) Prove that there is no 5regular simple planar graph with 14 vertices.
(Owens [1971])
 (+) Let $G$ be a 3connected 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) 3colorable.
 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.
 (!) 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 $2n4$ edges and facial triangles. (Hint: Use induction on the
number of facial triangles.)
 (!) Use Euler's formula to count the regions formed by $n$
pairwisecrossing 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 3regular graph with
crossing number 1 is 3edgecolorable
 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 kedgeconnected if no deletion of fewer than
$k$ edges disconnects it into two components that each contain a cycle.
Prove that if $G$ is a 4connected triangulation, then $G^*$ is
cyclically 4edgeconnected.
 (!) 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/21$.
(DeTempleRobertson [1974], GaskellKlamkinWatson [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_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 3dimensional 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 8vertex 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 8vertex 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. (BehzadMahmoodian [1969])
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 5coloring such that
the union of any two color classes induces a forest. Use this to prove the
conjecture of AlgorAlon [1989] that every planar graph decomposes into five
forests whose components are stars. (HakimiMitchemSchmeichel)
 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 computerassisted 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 3regular graph is 3edgecolorable
if and only if it is the union of two subgraphs in which every vertex has
even degree.
 (!) ChetwyndHilton [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 sidelength $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 3regular simple planar graph
is planar? What about 4regular 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 $2m1$ and edgechromatic
number $2m$.
 (+) Let $G$ be a 1factorable graph with even degree.
Prove that $L(G)$ is 1factorable. (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)$edgecoloring of $G'$ from a proper
$\Delta(G)$edgecoloring of $G'xy$. (K\ouml nig [1916])
 (+) An interval coloring of $G$ is a proper edgecoloring 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 HansonLotenToft [1998])
 Greedy edgecoloring obtains a proper edgecoloring 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
edgecoloring uses $2k1$ colors.
 A parity edgecoloring of a graph $G$ is an edgecoloring 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 edgecoloring such that on every cycle, every
color appears an even number of times. (K. Milans)
 With parity edgecoloring defined as above, let $p(G)$ denote
the minimum number of colors in a parity edgecoloring 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 $Gxy$ 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 Hamiltonianconnected.
 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
8cycle 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 10cycle. (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: LaiLiLu [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 3connected 3regular $n$vertex graph with
path cover number $n/9$.
 Prove that every 2connected, clawfree, pawfree graph is Hamiltonian
(GoodmanHedetniemi [1974])
 Prove that every $k$regular $k$edgeconnected graph is 1tough.
(Comment: Hence every such graph also has a 1factor.)
 Determine the maximum number of edges in a subgraph of $K_{n,n}$ having no
cycle of length $2n$. (EntringerSchmeichel [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 nonHamiltonian bipartite graph with minimum
degree $n/4$. (MoonMoser [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{(t1)n}$,
then $G$ is Hamiltonian. (source: ask Faudree)!>
 Use Example 7.2.14 (nonHamiltonian 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 n1$ whenever
$xy\notin E(G)$. Prove that $G$ has a perfect matching and that this may fail
when $n1$ is changed to $n2$. (Hint: Apply Ore's Theorem.)
 Construct a 3connected 4regular graph that is not Hamiltonian.
(Hint: Modify the Petersen graph.)
 Prove that there is a 3connected 3regular nonHamiltonian graph with $n$
vertices whenever $n$ is even and at least 10.
 Given that an $n$vertex graph with at least $\CH{n1}2+3$ edges is
Hamiltonianconnected, show that for each vertex pair $x,y$ there are
$x,y$paths of all lengths $2,\ldots,n1$. (JiangWest)
 (!) For even $n$, prove that if $G$ has vertex degrees $\VEC d1n$ in
nondecreasing order, and $d_i\ge i+t1$ for $1\le i\le n/21$, then $G$ has
$t$ edgedisjoint 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 $nm+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), 270273] 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 2edgeconnected outerplane graph is
3facecolorable.
 Let $G$ be a maximal plane graph other than $K_4$.
Prove that $G$ is 3facecolorable. (contributed by Michael
Pelsmajer)
 Prove that the vertices of every planar graph can be 2colored so that each
color class induces an outerplanar graph. (ChartrandGellerHedetniemi
[1971])
 Let $G$ be a 3regular graph. Prove that $G$ is 3edgecolorable
if and only if $G$ is the union of two even subgraphs. (Perhaps replace
7.3.20)
Section 8.1
 () Prove that $\omega(G)\ge 1+\Delta(G)/2$ for every clawfree 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 semiindependent sets of edges in a graph
$G$ is the family of independent sets of a matroid, where $X$ is
semiindependent 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 2coloring of the edges of $K_5$ that has
no monochromatic triangle consists of two monochromatic 5cycles.
 Let $n=R(k,l)$. Prove that the edges of the graph obtained
from $K_n$ by deleting one edge can be 2colored 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 2coloring of $E(K_{(m1)(n1)})$ (up to isomorphism) that
has no red $T$ or blue $K_n$. Conclude that if $G$
is formed from $K_{(m1)(n1)}$ 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 (m1)(n2)$ (HookIsaak [2010+])
 Show that $K_{5,5}$ has a 3edgecoloring with no monochromatic
$P_5$
 Prove that $R(C_5,K_4)=13$
(Comment: ErdosRousseauSchelp (see FaudreeSchelp [1978] (LMS 642))
conjectured that $R(C_m,K_n)=(m1)(n1)+1$ when
$m\ge n$ and $(m,n)\ne (3,3)$. This was proved for $n=4$ in
YangHuangZhang [1999], for $n=5$ in
BollobasJayawardeneYangHuangRousseauZhang [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 2coloring 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$. (CaroRoditty [2002])
 The zerosum 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 zerosum Ramsey numbers.)
a) Prove that $R(G,\ZZ_k)$ is welldefined 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 $2n1$, with equality for $n\in\{3,4\}$.
(Comment: In fact, equality holds for all $n$, which is not too messy
for odd $n$.) (LiTaoShen [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 8regular). 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
BaloghKaul [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 $n1$ dimensions. (EatonGrable)
 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
2choosable.) (KirovNaimi)
 The graph $\theta(l_1,\ldots,l_k)$ with branch vertices
$u$ and $v$ is the union of $k$ pairwise internallydisjoint
$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 3edgechoosable
 (addition to Exr8.4.20) Show that the join of this graph with $K_1$
is 3choosable. 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, p8485])
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 NPcomplete,
show that it is NPcomplete to find the maximum order of a common subgraph
in two input planar graphs.
 Prove for all fixed $k$ that it is NPcomplete to determine whether an
input graph has a $k$factor that is connected.
More to Come!