Modern Graph Theory — Homework 9

Loading…

Assignments: May 9th, 2026

Problem 1.

Prove: For

k\ge 2, every non-bipartite graph with

\delta(G)>\frac{2}{2k+1}n

contains an odd cycle of length at most 2k-1. **Proof.** Suppose, for contradiction, that G has no odd cycle of length at most 2k-1. Since G is non-bipartite, it contains an odd cycle. Let C be a shortest odd cycle in G, and write |C|=g. Then g\ge 2k+1. The cycle C has no chord. Indeed, any chord of C would split C into two cycles, one of which is an odd cycle shorter than C, contradicting the choice of C. We claim that every vertex outside C has at most two neighbors on C. If some vertex x\notin V(C) had three neighbors on C, these three neighbors would divide C into three arcs. Since C has odd length, at least one of these arcs has odd length. Together with the two edges from x to the endpoints of this arc, we obtain an odd cycle shorter than C (if the arc has length 1, this is just a triangle). This again contradicts the minimality of C. Now count the degrees of vertices on C. Since each vertex of C has degree at least \delta(G),

g\delta(G)\le \sum_{v\in V(C)}d(v).

On the other hand, C contributes exactly 2g to this degree sum, and every vertex outside C contributes at most 2 edges into C. Hence

\sum_{v\in V(C)}d(v)\le 2g+2(n-g)=2n.

Therefore

g\delta(G)\le 2n.

Using \delta(G)>\frac{2}{2k+1}n, we get

g<2k+1.

This contradicts g\ge 2k+1. Thus G must contain an odd cycle of length at most 2k-1. ∎ **Problem 2.** Prove: Let H be a graph consisting of an 8-cycle

C=v1v2\cdots v8v1

with chords v_1v_5 and v_2v_6. If a triangle-free graph G contains H as a subgraph, then

\delta(G)\le \frac{3}{8}n.

**Proof.** Let S=\{v_1,v_2,\ldots,v_8\} be the vertex set of the copy of H in G. First observe that \alpha(H)=3. Indeed, an independent set of size 4 in the 8-cycle must be one of the two alternating sets

{v1,v3,v5,v7},\qquad {v2,v4,v6,v8}.

But the first set contains the chord v_1v_5, and the second contains the chord v_2v_6. Hence no independent set in H has size 4. Since G is triangle-free, for every vertex x\in V(G), the set N_G(x)\cap S must be independent in H. Otherwise, if two vertices in N_G(x)\cap S were adjacent in H, then together with x they would form a triangle in G. Therefore

|N_G(x)\cap S|\le \alpha(H)=3

for every x\in V(G). Now count the edges from S to the whole graph, counting an edge inside S twice. On one hand,

\sum{i=1}^{8} dG(v_i)\ge 8\delta(G).

On the other hand,

\sum{i=1}^{8}dG(vi) =\sum{x\in V(G)} |N_G(x)\cap S| \le 3n.

Combining the two inequalities gives

8\delta(G)\le 3n,

so

\delta(G)\le \frac{3}{8}n.

∎

Download the original write-up here.

Problem 1.

Prove: For

k\ge 2, every non-bipartite graph with

\delta(G)>\frac{2}{2k+1}n

contains an odd cycle of length at most 2k-1. **Proof.** Suppose, for contradiction, that G has no odd cycle of length at most 2k-1. Since G is non-bipartite, it contains an odd cycle. Let C be a shortest odd cycle in G, and write |C|=g. Then g\ge 2k+1. The cycle C has no chord. Indeed, any chord of C would split C into two cycles, one of which is an odd cycle shorter than C, contradicting the choice of C. We claim that every vertex outside C has at most two neighbors on C. If some vertex x\notin V(C) had three neighbors on C, these three neighbors would divide C into three arcs. Since C has odd length, at least one of these arcs has odd length. Together with the two edges from x to the endpoints of this arc, we obtain an odd cycle shorter than C (if the arc has length 1, this is just a triangle). This again contradicts the minimality of C. Now count the degrees of vertices on C. Since each vertex of C has degree at least \delta(G),

g\delta(G)\le \sum_{v\in V(C)}d(v).

On the other hand, C contributes exactly 2g to this degree sum, and every vertex outside C contributes at most 2 edges into C. Hence

\sum_{v\in V(C)}d(v)\le 2g+2(n-g)=2n.

Therefore

g\delta(G)\le 2n.

Using \delta(G)>\frac{2}{2k+1}n, we get

g<2k+1.

This contradicts g\ge 2k+1. Thus G must contain an odd cycle of length at most 2k-1. ∎ **Problem 2.** Prove: Let H be a graph consisting of an 8-cycle

C=v1v2\cdots v8v1

with chords v_1v_5 and v_2v_6. If a triangle-free graph G contains H as a subgraph, then

\delta(G)\le \frac{3}{8}n.

**Proof.** Let S=\{v_1,v_2,\ldots,v_8\} be the vertex set of the copy of H in G. First observe that \alpha(H)=3. Indeed, an independent set of size 4 in the 8-cycle must be one of the two alternating sets

{v1,v3,v5,v7},\qquad {v2,v4,v6,v8}.

But the first set contains the chord v_1v_5, and the second contains the chord v_2v_6. Hence no independent set in H has size 4. Since G is triangle-free, for every vertex x\in V(G), the set N_G(x)\cap S must be independent in H. Otherwise, if two vertices in N_G(x)\cap S were adjacent in H, then together with x they would form a triangle in G. Therefore

|N_G(x)\cap S|\le \alpha(H)=3

for every x\in V(G). Now count the edges from S to the whole graph, counting an edge inside S twice. On one hand,

\sum{i=1}^{8} dG(v_i)\ge 8\delta(G).

On the other hand,

\sum{i=1}^{8}dG(vi) =\sum{x\in V(G)} |N_G(x)\cap S| \le 3n.

Combining the two inequalities gives

8\delta(G)\le 3n,

so

\delta(G)\le \frac{3}{8}n.

∎

Download the original write-up here.