Connectivity and Bipartite Graphs

The question

A festival needs two shifts of volunteers, and some pairs of volunteers cannot work together. Put each volunteer on a shift so that no clashing pair shares one. Here are five volunteers, numbered $1$ to $5$ , with an edge for each clash:

It cannot be done: volunteers $3$ , $4$ and $5$ clash pairwise, and three people do not fit on two shifts without two of them sharing. That triangle is a certificate of impossibility: a reader checks it in seconds. When a split is possible, the split itself is the certificate. This module proves that one of the two certificates always exists, and that a single search finds whichever one it is. Along the way it builds the vocabulary of walks, paths, cycles and components, and the first proof technique of the course: choose an extreme object.

Walks, paths and components

In this course a graph is simple unless we say otherwise: no loops and no two edges joining the same pair of vertices. (Several statements below are false for multigraphs: two vertices joined by three parallel edges have minimum degree 3 and no cycle in our sense.)

A walk is a sequence of vertices in which consecutive vertices are adjacent; it may repeat vertices and edges. A trail repeats no edge, and a path repeats no vertex. A walk is closed if it ends where it starts, and a cycle is a closed walk of length at least 3 that repeats no vertex except the first and last.

Lemma. Every $u, v$ -walk contains a $u, v$ -path.

Proof. Among all $u, v$ -walks that use only vertices and edges of the given walk, take one of minimum length. If it repeated a vertex $x$ , cutting out the closed piece between the two visits to $x$ would give a shorter $u, v$ -walk from the same material, contradicting minimality. So it repeats no vertex: it is a path. $◻$

So "there is a walk from $u$ to $v$ " and "there is a path from $u$ to $v$ " mean the same thing. That relation is an equivalence: every vertex reaches itself, reaching is symmetric (reverse the walk), and it is transitive (follow one walk, then the other; the result is a walk, and the lemma turns it into a path). Its classes split the vertices; the subgraphs they induce are the components, and $G$ is connected if it has one component.

Notice the order of the argument. Transitivity is easy for walks and awkward for paths: two paths glued end to end can cross each other. Working with walks and then cleaning up with the lemma is a pattern you will meet again in this module.

Predict: if you delete one edge from a connected graph, how many components can the result have?

One or two, never more. The deleted edge $u v$ was the only thing that could matter: every other walk survives, and a walk that used $u v$ can be rerouted unless $u$ and $v$ end up separated. So the vertices still reaching $u$ form one component and those still reaching $v$ form at most one more. (Deleting a vertex is different: it can create many components.)

The longest-path trick

The minimum degree $δ (G)$ is the smallest degree of any vertex.

Lemma. If a simple graph $G$ has $δ (G) \geq 2$ , then $G$ contains a cycle. More generally, if $δ (G) \geq k$ for some $k \geq 2$ , then $G$ contains a cycle of length at least $k + 1$ .

Proof. $G$ is finite, so it has a longest path $P = v_{0} v_{1} \dots v_{m}$ . Every neighbor of $v_{0}$ lies on $P$ : a neighbor off $P$ would extend $P$ to a longer path. Since $d (v_{0}) \geq k$ , the vertex $v_{0}$ has at least $k$ neighbors among $v_{1}, \dots, v_{m}$ . Let $v_{i}$ be the one with the largest index; then $i \geq k$ . The path $v_{0} v_{1} \dots v_{i}$ and the edge $v_{i} v_{0}$ form a cycle of length $i + 1 \geq k + 1$ . $◻$

Proof moves used here.

Extremal choice. A longest path turns "maximum" into a fact about its endpoint: no neighbor is off the path. The same move appears in every module of this course.
Pigeonhole. At least $k$ neighbors among $v_{1}, \dots, v_{m}$ force one of them to have index at least $k$ .

Predict: a simple graph has minimum degree 4. Must it contain a cycle of length at least 5?

Yes: take $k = 4$ in the lemma. The end of a longest path has four neighbors on the path, and the farthest of them is at least 4 steps back. $K_{5}$ shows the bound is tight: its longest cycle has length exactly 5.

Odd closed walks contain odd cycles

Lemma. Every closed walk of odd length contains a cycle of odd length.

Proof. By strong induction on the length $ℓ$ of the closed walk $W$ . If $W$ repeats no vertex except its ends, it is a cycle (a closed walk of odd length in a graph without loops has length at least 3), and it is odd. Otherwise some vertex $x$ appears twice inside $W$ . Split $W$ at those two visits into two closed walks through $x$ . Their lengths add up to $ℓ$ , which is odd, so one of them has odd length. It is shorter than $W$ , so by induction it contains an odd cycle, which is also in $W$ . $◻$

Proof moves used here. Induction on the length, and parity: two numbers adding up to an odd number cannot both be even.

Predict: can a closed walk of even length contain an odd cycle?

Yes. Go around a triangle twice: the closed walk has length 6 and is made of a triangle. The lemma only goes one way; an even closed walk tells you nothing. That is why the bipartite test below looks for a single odd closed walk.

König's characterization, traced on the house

A graph is bipartite if its vertices split into two sets $X$ and $Y$ with every edge joining $X$ to $Y$ — two shifts with no clash inside a shift.

König's theorem (1936)

A simple graph is bipartite if and only if it has no cycle of odd length.

Proof. Only if. Walking around a cycle, the vertices alternate between $X$ and $Y$ , so the cycle returns to its start after an even number of steps.

If. It is enough to two-color each component. Pick a vertex $r$ , and put each vertex $v$ of its component in $X$ if its distance $d (r, v)$ is even and in $Y$ if it is odd. Suppose an edge $u v$ joins two vertices of the same set. Then a shortest $r, u$ -path, the edge $u v$ , and a shortest $v, r$ -path form a closed walk of length $d (r, u) + 1 + d (r, v)$ , which is odd because $d (r, u)$ and $d (r, v)$ have the same parity. By the previous lemma it contains an odd cycle. So if there is no odd cycle, every edge joins $X$ to $Y$ . $◻$

A breadth-first search computes the distances. On the house, from $r = 1$ :

Vertices 3 and 5 are both at distance 2 and are adjacent. The tree paths 3, 2, 1 and 5, 4, 1 with the edge 3-5 close the odd cycle 3, 2, 1, 4, 5.

from collections import deque

def network(edges):
    g = {}
    for u, v in edges:
        g.setdefault(u, set()).add(v)
        g.setdefault(v, set()).add(u)
    return g

def distances(g, r):
    dist, queue = {r: 0}, deque([r])
    while queue:
        u = queue.popleft()
        for w in sorted(g[u]):
            if w not in dist:
                dist[w] = dist[u] + 1
                queue.append(w)
    return dist

H = network([(1, 2), (2, 3), (3, 4), (4, 1), (3, 5), (4, 5)])
d = distances(H, 1)
assert d == {1: 0, 2: 1, 4: 1, 3: 2, 5: 2}
clashes = [(u, v) for u in H for v in H[u] if u < v and d[u] % 2 == d[v] % 2]
assert clashes == [(3, 5)]
cycle = [3, 2, 1, 4, 5]                    # tree path 3, 2, 1, then 1, 4, 5, closed by the edge 5-3
assert all(cycle[(i + 1) % 5] in H[cycle[i]] for i in range(5)) and len(cycle) % 2 == 1

The search found a 5-cycle, not the triangle $3, 4, 5$ . It returns an odd cycle, which is all the certificate needs; it does not promise the shortest one.

On a ladder with two rails of four rungs (vertices $a_{1}, \dots, a_{4}$ and $b_{1}, \dots, b_{4}$ , with rails $a_{i} a_{i + 1}$ , $b_{i} b_{i + 1}$ and rungs $a_{i} b_{i}$ ) the same search finds no clash: the parity of the distance from $a_{1}$ is a two-coloring.

ladder = network([(f"a{i}", f"a{i + 1}") for i in range(1, 4)] + [(f"b{i}", f"b{i + 1}") for i in range(1, 4)]
                 + [(f"a{i}", f"b{i}") for i in range(1, 5)])
dl = distances(ladder, "a1")
assert all(dl[u] % 2 != dl[v] % 2 for u in ladder for v in ladder[u])
assert sorted(v for v in ladder if dl[v] % 2 == 0) == ["a1", "a3", "b2", "b4"]

Proof moves used here. Certificate pair: a two-coloring proves "bipartite" and an odd cycle proves "not bipartite", and the proof shows one of them always exists. Extremal choice again: shortest paths from $r$ give the distances whose parity does the work.

The degree-sum formula

Proposition. In every graph, the degrees add up to twice the number of edges: $\sum_{v} d (v) = 2 e (G)$ .

Proof. Count pairs (vertex, edge at that vertex) in two ways. Grouped by vertex, there are $\sum_{v} d (v)$ of them. Grouped by edge, each edge has exactly two ends, so there are $2 e (G)$ . $◻$

A consequence: every graph has an even number of vertices of odd degree, because the degrees add up to an even number. At a party where five people shook hands with 1, 2, 2, 3 and 3 others, the odd counts 1, 3, 3 make three odd degrees, so someone misremembered. Notice what kind of argument this is. It rules out a whole family of graphs without looking at any of them, by counting one quantity two ways and comparing parities. In $H$ the degrees are $2, 2, 3, 3, 2$ , which add up to $12 = 2 \cdot 6$ .

assert sum(len(H[v]) for v in H) == 2 * 6
assert sum(1 for v in H if len(H[v]) % 2 == 1) % 2 == 0

Proof move used here. Double counting.

What a certificate costs

Trying every split of $n$ volunteers into two shifts means $2^{n - 1}$ splits. The search above visits each vertex and each edge a constant number of times, $O (n + m)$ , and hands back either a two-coloring or an odd cycle. Either one is checked in $O (n + m)$ by anyone who doubts it.

A problem that looks different

A knight starts on a square of a chessboard and makes some moves. Can it ever be back on its starting square after an odd number of moves? Nothing in the question mentions shifts or clashes. The lab's last exercise is a different problem that also hides its structure.

Practise

The lab runs in your browser. Your code runs the search, coloring one distance layer per frame, and returns either a two-coloring or a genuine odd cycle. Then it finds a long cycle in a graph of large minimum degree. Half of the lab is proofs: assemble one about vertices of odd degree, find the false step in a convincing argument, and write one for a problem that names no technique.

Recap

You can now: turn a walk into a path; prove that minimum degree $k \geq 2$ forces a cycle of length at least $k + 1$ ; prove that odd closed walks contain odd cycles; prove König's theorem and run it as a search; and count with the degree-sum formula.
Invariant: in the search, a vertex's side is the parity of its distance from the start, and an edge inside one side closes an odd walk.
Complexity achieved: a two-coloring or an odd cycle in $O (n + m)$ , against $2^{n - 1}$ splits by brute force; either certificate is checked in $O (n + m)$ .
Failure mode: reporting a closed walk as a cycle (it may repeat vertices), and assuming the search returns the shortest odd cycle.
In real software: NetworkX's bipartite.color (which is_bipartite calls) two-colors a graph by a search that gives each newly reached vertex the color opposite its neighbor's, and reports a same-colored edge as "not bipartite".
Next: module 4 uses the degree-sum formula's parity to decide when a graph can be drawn without lifting the pen.

Check yourself

After the lab, the tutor will ask you to defend your work out loud:

In the proof of "walk contains path", why must the shorter walk use only the material of the original walk?
Why does the longest-path proof need the path to be longest, and where exactly is that used?
The search found the 5-cycle $3, 2, 1, 4, 5$ in the house rather than the triangle. Why is that still a valid certificate?

Topic list modeled on the public syllabus of UIUC Math 412 (Graph Theory), which follows D. B. West, Introduction to Graph Theory, 2nd ed., Chapters 1–7. All lessons, proofs, examples, code and exercises here are original. This course is independent and not affiliated with or endorsed by the University of Illinois.