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. 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
$
\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 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=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^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.
- Determine the number of maximum-sized independent sets of vertices
in the Petersen graph.
- Determine the minimum number of vertices that must be deleted from the
Petersen graph to reduce the independence number.
- (+) Let $A$ be the adjacency matrix of a simple graph $G$.
a) Prove that $A$ is the incidence matrix of some simple graph if and
only if $G$ is 2-regular and has no 4-cycle.
b) Determine the conditions under which $A$ is the incidence matrix
of $G$ itself.
- The 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.
- 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
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 a list of $n$ positive numbers with largest element $r$ and even
sum is graphic if $n\ge r^2$. (Sivaraman [2013]; see Zverovich-Zverovich [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. (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$.
- (+) Prove that an even graph with $n$ vertices and $m$ edges
decomposes into at most $n\log m$ cycles.
- (!) Let $n$ and $k$ be positive integers such that $n$ is divisible by
$k-1$. 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 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])
- 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 3-regular
bipartite simple graph can be obtained from a graph whose components are
isomorphic to $K_{3,3}$ by repeated bridging operations. (Kotzig [1966])
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])
- 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 $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 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 $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 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,m-d(v)$} and
$\epsilon_m(v)$=max{$0,d(v)-m$}. Let $G$ be a
bipartite graph with partite sets $X$ and $Y$ of equal size.
Prove that if there is a positive integer $m$ such that
$\sum_{x\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 $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. (C-T [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.)
- 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 3-regular 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 $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])
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|\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.)
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$.
- 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)
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.
More to Come!