Modern Graph Theory — Homework 8

Loading…

Modern Graph Theory — Homework 8

Assignments: Apr 28th, 2026

Problem 1.

The odd-girth of a graph is the length of its shortest odd cycle. For any subset

U\subset V(G), let G[U] denote the subgraph of G induced on U. Let G be a graph of odd-girth at least 2k+3. Assume that for any independent set I of G, G-I contains an odd cycle. Let A and B be two disjoint independent sets of G with |A\cup B| maximized. Let C be an odd cycle in G-A. Choose a vertex v\in V(C) and define a BFS tree rooted at v in G. Let

Li={u\in V(G):\operatorname{dist}(u,v)=i},\qquad L0={v}.

For each 1\le i\le k, let

Ji:= \left(\bigcup{0\le j<i}Lj\right) \cup (Li\cap B) \cup \left(\bigcup{j>i}\bigl(Lj\cap (A\cup B)\bigr)\right).

Prove the following claims. 1. Each L_i is an independent set for each i\le k. 2. The subgraph G[J_i] is bipartite. 3. |A\cup B|\ge |J_i| and |J_i\setminus (A\cup B)|\ge i-1. 4. |L_i\cap A|\ge i-1 and thus |A|\ge \frac{k(k-1)}{2}. 5. The graph G has at least k^2 vertices. Before our ** Proof** , we have the following idea: **Idea.** The BFS tree only concerns the component which contains v. Denote this component by R. When we compare J_i with A\cup B, we may do the comparison inside R: if A\cap R and B\cap R were not maximal in R, then we could improve A and B in the whole graph by changing them only in this component. The main point is that an edge inside a low BFS level would create a short odd cycle. Hence the first k levels behave like the levels of a bipartite graph. The set J_i is built by replacing L_i\cap A with some earlier vertices. Maximality of A\cup B then forces L_i\cap A to be large. **Proof.** **(1)** Fix i\le k. Suppose that there is an edge xy with x,y\in L_i. Let P_x and P_y be shortest paths from v to x and y, respectively. Let w be the last common vertex of these two paths. Then the two subpaths from w to x and from w to y, together with the edge xy, form an odd cycle. Its length is at most

i+i+1=2i+1\le 2k+1,

contradicting that the odd-girth of G is at least 2k+3. Therefore no such edge exists, and L_i is independent. **(2)** In a BFS layering, every edge joins vertices either in the same level or in two consecutive levels. By (1), there are no edges inside L_0,L_1,\ldots,L_k. Fix 1\le i\le k. Define

X=\left(\bigcup{\substack{0\le j<i\ j\equiv i\pmod 2}}Lj\right) \cup \left(B\cap \bigcup{j\ge i}Lj\right),

and

Y=\left(\bigcup{\substack{0\le j<i\ j\not\equiv i\pmod 2}}Lj\right) \cup \left(A\cap \bigcup{j>i}Lj\right).

Then J_i=X\cup Y. On the levels L_0,\ldots,L_{i-1}, this is just the usual parity coloring of BFS levels, so edges between these levels go from X to Y. For the vertices after level i, we put the vertices of B in X and the vertices of A in Y; this causes no edge inside one part since both A and B are independent. Finally, any edge from the earlier levels to L_i\cap B must come from L_{i-1}, which lies in Y. Hence every edge of G[J_i] goes between X and Y. So G[J_i] is bipartite. **(3)** Since G[J_i] is bipartite, its two color classes form two disjoint independent sets. By the maximality of A and B,

|A\cup B|\ge |J_i|.

It remains to show that J_i contains at least i-1 vertices outside A\cup B. Since C\subseteq G-A, no vertex of C belongs to A. Starting from v, take the i-1 vertices before v and the i-1 vertices after v on the cycle C. Since |C|\ge 2k+3>2i-1, these vertices together with v form a path on 2i-1 distinct vertices. Each of them has distance at most i-1 from v, hence lies in

\bigcup{0\le j<i}Lj\subseteq J_i.

On a path with 2i-1 vertices, an independent set can contain at most i vertices. Since B is independent, at most i of the above vertices lie in B. Thus at least (2i-1)-i=i-1 of them lie in neither A nor B. Therefore

|J_i\setminus (A\cup B)|\ge i-1.

**(4)** Now compare J_i with (A\cap R)\cup(B\cap R). By the definition of J_i, among the vertices of (A\cap R)\cup(B\cap R), the only ones not included in J_i are precisely the vertices of L_i\cap A. Thus

((A\cap R)\cup(B\cap R))\setminus Ji=Li\cap A.

Since J_i is bipartite by (2), its two color classes are two disjoint independent sets in R. By the maximality of (A\cap R)\cup(B\cap R) inside R,

|(A\cap R)\cup(B\cap R)|\ge |J_i|.

Using

|S|-|T|=|S\setminus T|-|T\setminus S|

with S=(A\cap R)\cup(B\cap R) and T=J_i, we get

|L_i\cap A|

=|((A\cap R)\cup(B\cap R))\setminus Ji| \ge |Ji\setminus (A\cup B)| \ge i-1.

Since the BFS levels are disjoint, we can sum these inequalities over i=1,\ldots,k:

|A|\ge \sum_{i=1}^{k}|L_i\cap A|

\ge \sum_{i=1}^{k}(i-1) =\frac{k(k-1)}{2}.

**(5)** The same argument can be applied with the roles of A and B interchanged. Indeed, B is independent, so by assumption G-B contains an odd cycle. Repeating (1)--(4) with A and B switched gives

|B|\ge \frac{k(k-1)}{2}.

Moreover, C\subseteq G-A has length at least 2k+3. Since B is independent, B contains at most k+1 vertices of this odd cycle. Thus at least k+2 vertices of C are outside B. They are also outside A, because C\subseteq G-A. Therefore

|V(G)|\ge |A|+|B|+k+2

\ge k(k-1)+k+2 =k^2+2 \ge k^2.

∎

PDF

Download the original write-up here.

Assignments: Apr 28th, 2026

Problem 1.

The odd-girth of a graph is the length of its shortest odd cycle. For any subset

U\subset V(G), let G[U] denote the subgraph of G induced on U. Let G be a graph of odd-girth at least 2k+3. Assume that for any independent set I of G, G-I contains an odd cycle. Let A and B be two disjoint independent sets of G with |A\cup B| maximized. Let C be an odd cycle in G-A. Choose a vertex v\in V(C) and define a BFS tree rooted at v in G. Let

Li={u\in V(G):\operatorname{dist}(u,v)=i},\qquad L0={v}.

For each 1\le i\le k, let

Ji:= \left(\bigcup{0\le j<i}Lj\right) \cup (Li\cap B) \cup \left(\bigcup{j>i}\bigl(Lj\cap (A\cup B)\bigr)\right).

Prove the following claims. 1. Each L_i is an independent set for each i\le k. 2. The subgraph G[J_i] is bipartite. 3. |A\cup B|\ge |J_i| and |J_i\setminus (A\cup B)|\ge i-1. 4. |L_i\cap A|\ge i-1 and thus |A|\ge \frac{k(k-1)}{2}. 5. The graph G has at least k^2 vertices. Before our ** Proof** , we have the following idea: **Idea.** The BFS tree only concerns the component which contains v. Denote this component by R. When we compare J_i with A\cup B, we may do the comparison inside R: if A\cap R and B\cap R were not maximal in R, then we could improve A and B in the whole graph by changing them only in this component. The main point is that an edge inside a low BFS level would create a short odd cycle. Hence the first k levels behave like the levels of a bipartite graph. The set J_i is built by replacing L_i\cap A with some earlier vertices. Maximality of A\cup B then forces L_i\cap A to be large. **Proof.** **(1)** Fix i\le k. Suppose that there is an edge xy with x,y\in L_i. Let P_x and P_y be shortest paths from v to x and y, respectively. Let w be the last common vertex of these two paths. Then the two subpaths from w to x and from w to y, together with the edge xy, form an odd cycle. Its length is at most

i+i+1=2i+1\le 2k+1,

contradicting that the odd-girth of G is at least 2k+3. Therefore no such edge exists, and L_i is independent. **(2)** In a BFS layering, every edge joins vertices either in the same level or in two consecutive levels. By (1), there are no edges inside L_0,L_1,\ldots,L_k. Fix 1\le i\le k. Define

X=\left(\bigcup{\substack{0\le j<i\ j\equiv i\pmod 2}}Lj\right) \cup \left(B\cap \bigcup{j\ge i}Lj\right),

and

Y=\left(\bigcup{\substack{0\le j<i\ j\not\equiv i\pmod 2}}Lj\right) \cup \left(A\cap \bigcup{j>i}Lj\right).

Then J_i=X\cup Y. On the levels L_0,\ldots,L_{i-1}, this is just the usual parity coloring of BFS levels, so edges between these levels go from X to Y. For the vertices after level i, we put the vertices of B in X and the vertices of A in Y; this causes no edge inside one part since both A and B are independent. Finally, any edge from the earlier levels to L_i\cap B must come from L_{i-1}, which lies in Y. Hence every edge of G[J_i] goes between X and Y. So G[J_i] is bipartite. **(3)** Since G[J_i] is bipartite, its two color classes form two disjoint independent sets. By the maximality of A and B,

|A\cup B|\ge |J_i|.

It remains to show that J_i contains at least i-1 vertices outside A\cup B. Since C\subseteq G-A, no vertex of C belongs to A. Starting from v, take the i-1 vertices before v and the i-1 vertices after v on the cycle C. Since |C|\ge 2k+3>2i-1, these vertices together with v form a path on 2i-1 distinct vertices. Each of them has distance at most i-1 from v, hence lies in

\bigcup{0\le j<i}Lj\subseteq J_i.

On a path with 2i-1 vertices, an independent set can contain at most i vertices. Since B is independent, at most i of the above vertices lie in B. Thus at least (2i-1)-i=i-1 of them lie in neither A nor B. Therefore

|J_i\setminus (A\cup B)|\ge i-1.

**(4)** Now compare J_i with (A\cap R)\cup(B\cap R). By the definition of J_i, among the vertices of (A\cap R)\cup(B\cap R), the only ones not included in J_i are precisely the vertices of L_i\cap A. Thus

((A\cap R)\cup(B\cap R))\setminus Ji=Li\cap A.

Since J_i is bipartite by (2), its two color classes are two disjoint independent sets in R. By the maximality of (A\cap R)\cup(B\cap R) inside R,

|(A\cap R)\cup(B\cap R)|\ge |J_i|.

Using

|S|-|T|=|S\setminus T|-|T\setminus S|

with S=(A\cap R)\cup(B\cap R) and T=J_i, we get

|L_i\cap A|

=|((A\cap R)\cup(B\cap R))\setminus Ji| \ge |Ji\setminus (A\cup B)| \ge i-1.

Since the BFS levels are disjoint, we can sum these inequalities over i=1,\ldots,k:

|A|\ge \sum_{i=1}^{k}|L_i\cap A|

\ge \sum_{i=1}^{k}(i-1) =\frac{k(k-1)}{2}.

**(5)** The same argument can be applied with the roles of A and B interchanged. Indeed, B is independent, so by assumption G-B contains an odd cycle. Repeating (1)--(4) with A and B switched gives

|B|\ge \frac{k(k-1)}{2}.

Moreover, C\subseteq G-A has length at least 2k+3. Since B is independent, B contains at most k+1 vertices of this odd cycle. Thus at least k+2 vertices of C are outside B. They are also outside A, because C\subseteq G-A. Therefore

|V(G)|\ge |A|+|B|+k+2

\ge k(k-1)+k+2 =k^2+2 \ge k^2.

∎

PDF

Download the original write-up here.

Modern Graph Theory — Homework 8

Search

Modern Graph Theory — Homework 8

Assignments: Apr 28th, 2026

PDF

Assignments: Apr 28th, 2026

PDF