Skip to main content

Discrete Mathematics · Graphs, trees, connectivity, and matchings

BFS two-coloring is the certificate that no odd cycle exists

Problem

Discrete Mathematics practice problem

A graph is bipartite when its vertices can be partitioned into two independent sets. Equivalently, the vertices admit a 22-coloring in which every edge is bichromatic.

1. Prove that a graph GG is bipartite if and only if GG contains no odd cycle. For the forward direction, show that an odd cycle cannot be 22-colored. For the converse, run breadth-first search independently in each connected component, color a vertex red or blue according to the parity of its BFS distance from the component root, and prove that a monochromatic edge would produce an odd closed walk and hence an odd cycle.

2. Let G0G_0 have vertex set {1,2,3,4,5,6,7}\{1,2,3,4,5,6,7\} and edge set{1−2, 1−3, 2−4, 2−5, 3−5, 3−6, 4−7, 5−7, 6−7}.\{1{-}2,\ 1{-}3,\ 2{-}4,\ 2{-}5,\ 3{-}5,\ 3{-}6,\ 4{-}7,\ 5{-}7,\ 6{-}7\}.Run BFS from vertex 11. Record the layer of every vertex, the resulting 22-coloring, and the two color classes. Verify every edge of G0G_0 against that coloring, and conclude that G0G_0 is bipartite. The certificate must be the BFS layering, not an unspecified greedy coloring.

3. Let HH be the 55-cycle on vertices {p,q,r,s,t}\{p,q,r,s,t\} with edges pq,qr,rs,st,tppq,qr,rs,st,tp. Run BFS from pp, record colors by layer parity, and exhibit the first monochromatic edge that BFS detects. Extract an explicit odd cycle (the whole vertex set of HH is acceptable) and conclude that HH is not bipartite.

4. Audit the claim 'G0G_0 has no triangles, therefore G0G_0 is bipartite' and the claim 'HH contains a cycle, therefore HH is not bipartite'. Identify the missing length hypothesis. Do not treat an even cycle as an obstruction, and do not replace the BFS certificate by a matching argument or by Hall's theorem.

Hint

Hint

If a monochromatic edge abab appears in a BFS coloring, the two rootward paths plus abab form a closed walk whose length is odd because dist⁡(a)\operatorname{dist}(a) and dist⁡(b)\operatorname{dist}(b) have the same parity.

Check your work

Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.

The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Discrete Mathematics sample problem: Try the free sample problem.

More Discrete Mathematics practice problems

Back to Discrete Mathematics

An original ProofAnvil practice problem, written for this course. ProofAnvil is a practice course, not a homework-answer service.