CSL 7410: Graph Theory and Applications
Homework 2
Due: 20/10/2024 11:59 PM
Instructor: Tanmay Inamdar
Instructions: I strongly encourage using LaTeX for the assignments; otherwise submit homeworks in
clean and legible handwriting. I will expect precise, concise, and mathematically formal answers. You may
receive partial credit for having the correct proof idea.
Examples are not proofs and will receive 0 credit.
Collaboration and using outside sources. The homework will be graded individually. You can
discuss the questions with your classmates/TAs/me, but only after you have given sufficient thought
(at least 1 hour per question).
If you find a solution online or in one of the sources, you must clearly acknowledge the source; this also
includes discussions with me/others. Even if you discuss or find the answer online, do not copy the entire
solution. Get the initial idea, develop it yourself, and write it in your own words.
Lateness policy. You are allowed 4 late days across all homeworks combined, and late days
are rounded up (e.g., if you submit on 21/10/2024 at 12:05 AM, it will be counted as 1 day late).
If you go above 4 days overall, you will be marked 0 for all homeworks from that point onwards, regardless
of any reason (valid or not).
Total points: 50.
Assume that all graphs mentioned below are simple and undirected.
1. 14 points
This is closely related to the Q1(a) from the minor exam. There are two parts to the question.
Let G = (V, E) be a bipartite graph with bipartition {A, B}. Let A1 ⊆ A be a subset with the following
property: (i) there is a matching, say M1, that saturates A1, and (ii) for any strict superset of A1, say
A′
1
, there is no matching that saturates A′
1
. That is, A1 is inclusion-wise maximal subset of A that
has a matching saturating it.
(a) Prove that M1 is in fact a maximum matching.
(b) Let A2 be another inclusion-wise maximal subset of A that has a matching, say M2, saturating
it, and further A1 ̸= A2.
Then, prove that, the set of endpoints of M1 and M2 in the “B-side” are the same.
A bit more formally, if B1 ⊆ B and B2 ⊆ B are the endpoints of M1 and M2 in B, then prove
that B1 = B2.
2. 5 points
Let G = (V, E) be an Eulerian graph. Then, prove that we can partition the set of edges E into
edge-disjoint cycles.
That is, E can be partitioned as {C1, C2, . . . , Ck}, where each Ci ⊆ E forms a cycle in G.
Note that since it is a partition, it must hold that, C1 ∪C2 ∪. . .∪Ck = E, and Ci ∩Cj = ∅ for Ci ̸= Cj .
1
3. 4 points
For each of the following, give an example of a graph that satisfies the stated property.
(a) Eulerian and Hamiltonian
(b) Eulerian but not Hamiltonian
(c) Hamiltonian but not Eulerian
(d) Neither Eulerian nor Hamiltonian
4. 5 points
Recall the “thought-experiment” algorithm that we used in the proof of Ore’s theorem and Chv´atal’s
theorem, where, in each iteration, we add an edge between non-neighbors, if the addition of that edge
still keeps the graph non-Hamiltonian.
Suppose in some iteration, we have a graph Gold and then we add a new edge uv such that u and v
are non-neighbors in Gold, then Gnew = Gold + uv.
Let (d1, d2, . . . , dn) be the degree sequence of Gold and (d
′
1
, d′
2
, . . . , d′
n
) be the degree sequence of Gnew.
Suppose the old degree sequence satisfies the following condition as in Chv´atal’s theorem:
for every i such that 1 ≤ i <
n
2
, di ≤ i =⇒ dn−i ≥ n − i.
Then prove that, the new degree sequence also satisfies the similar condition.
for every i such that 1 ≤ i <
n
2
, d′
i ≤ i =⇒ d
′
n−i ≥ n − i.
5. Total 14 points
This question is about a class of graphs, called degenerate graphs. First, we will see three different
definitions, and you are asked to show that they are equivalent. Then, you will be asked to show
different properties of this class of graphs.
v1
v2 v3 vi−1 vi vi+1 vj
“left degree” of vi is equal to 3
“right degree” of vi
is large vn
. . . . . .
Figure 1: An example of a 3-degeneracy ordering, where only the edges incident to vi are shown.
“Left degree” of vi
is 3. Note that “right degree” of vi can be pretty large.
(a) 5 points
Let d ≥ 1 be an integer.
Definition 1 A graph G = (V, E) is called a d-degenerate graph if, for every induced subgraph
H of G, the minimum degree of H is at most d.
Definition 2 A graph G = (V, E) is called a d-degenerate graph if, for every subgraph H of G,
the minimum degree of H is at most d.
Definition 3 A graph G = (V, E) is called a d-degenerate graph if the vertices can be ordered as
v1, v2, . . . , vn with the following property: for each 1 ≤ i ≤ n, the number of neighbors of vi to the
“left of ” vi is at most d. More formally, for each 1 ≤ i ≤ n, | {vj : {vi
, vj} ∈ E, j < i} | ≤ d. Such
an ordering is called a “d-degeneracy ordering”. See figure 1.
2
Show that the three definitions of d-degenerate graphs are equivalent to each other. That is, show
that G satisfies definition 1 iff G satisfies definition 2 iff G satisfies definition 3.
(b) 8 points
Properties of d-degenerate graphs.
(i) Let G = (V, E) be a d-degenerate graph with n vertices. Show that |E| ≤ nd.
(ii) Show that a graph of maximum degree ∆ is ∆-degenerate.
(iii) Give an example of a d-degenerate graph with maximum degree larger than d.
(iv) Give a polynomial-time algorithm to find a d-degeneracy ordering of a d-degenerate graph.
(c) 6 points
Recall the greedy coloring algorithm from the class, where in the first line we fix some arbitrary
order of vertices.
If we run the algorithm using the d-degeneracy ordering of G, then show that the algorithm
produces a (d + 1)-coloring of G.
Note that due to questions (b.ii) and (b.iii), this result generalizes what we showed in the class.
6. 8 points
In this question, we will work out the details of Mycielski’s construction, which shows the following:
For every k ≥ 1, there exists a triangle-free graph Gk such that χ(Gk) = k.
This construction is done inductively as follows.
In the base case, for k = 1 and k = 2, let G1 be an isolated vertex, and G2 be two vertices connected
by an edge.
Part 1. Show that G1, G2 satisfy the claim. 0.5 points
Inductive step. Now, suppose for some k ≥ 3 we have inductively constructed a graph Gk−1 that is
triangle-free, and χ(Gk−1) = k − 1, and suppose Gk−1 has vertices u1, u2, . . . , uℓ
. We construct Gk by
adding some new vertices and edges to the graph Gk−1.
(a) Add ℓ + 1 new vertices v1, v2, . . . , vℓ
, and w.
(b) If ui and uj are adjacent in Gk−1, then add edges viuj and uivj .
(c) Add edges between w and vi for every 1 ≤ i ≤ ℓ.
Part 2. We want to show that Gk is triangle-free and χ(Gk) = k.
• Part 2a. Showing Gk is triangle-free.
Suppose for contradiction, Gk contains a triangle T = {x, y, z}. Then, from the way we added
the edges, consider different cases for the vertices x, y, z.
In each case, find a triangle in Gk−1 as well, which is a contradiction, since by assumption Gk−1
is triangle-free. 1.5 points
• Part 2b. Showing χ(Gk) ≤ k.
Let f : V (Gk−1) → {1, 2, . . . , k − 1} be a (k − 1)-coloring of Gk−1. Let f
′
: V (Gk) → {1, 2, . . . , k}
be defined as follows:
f
′
(x) =



f(x) if x ∈ V (Gk−1)
f(ui) if x = vi
k if x = w
Show that f
′
is a proper k-coloring of Gk. 1.5 points
• Part 2c. Showing that χ(Gk) ≥ k.
Suppose for contradiction that χ(Gk) < k. Then, it must be the case that χ(Gk) = k −1. Argue
why. 1 point
3
Then, let h : V (Gk) → {1, 2, . . . , k − 1} be a (k − 1)-coloring of Gk.
Define g : V (Gk−1) → {1, 2, . . . , k − 2} as follows.
g(ui) = (
h(vi) if h(vi) ̸= k − 1
h(ui) if h(vi) = k − 1
Show that g is a valid (k − 2)-coloring of Gk−1, which will give the resulting contradiction.
2 points
Note: In each of the questions above, you will have to think about how we constructed Gk from Gk−1
– what kind of vertices and edges were added, which will be required for showing claims and reaching
contradictions.
Part 3. Draw G3 and G4 using the construction described above. 1.5 points
4   solution of the all the problems