Tutte's Theorem and Factors

The question: balanced degrees, impossible pairing

Twenty-two devices have a compatibility graph in which every device has exactly three neighbors. Can they all be paired off along compatible links? The order is even and every degree is the same, so nothing obvious stands in the way. In a bipartite graph that would settle it: module 11 showed that a regular bipartite graph of positive degree has a perfect matching. This graph is not bipartite, and the answer is no.

Here is the graph, $T$. Take three copies, labeled $A$, $B$, $C$, of a seven-vertex gadget: join each of $0,1,2$ to each of $3,4,5$, then replace the edge from $0$ to $3$ by a path through a new vertex $x$. Finally add one hub $h$ and join it to the vertex $x$ of each copy.

The six numbered vertices of a gadget keep degree three. Its vertex $x$ has two neighbors inside the gadget and one at the hub, and the hub has degree three as well: twenty-two vertices, thirty-three edges, every degree three. Now delete $h$. What remains is three separate components of seven vertices each. Seven is odd, so no component can pair all of its vertices internally: each one needs a partner outside itself for at least one vertex, and the only vertex outside is $h$. But $h$ can be in only one pair. So $T$ has no perfect matching.

That argument is evidence a reader can check in a minute, without trying a single matching. This module turns it into Tutte's condition, which decides exactly when a graph has a perfect matching, and then changes direction and builds spanning cycles in graphs of even regular degree.

vertices = ['h']; edges = []
for label in ('A','B','C'):
    left = [label+str(i) for i in range(3)]
    right = [label+str(i) for i in range(3,6)]
    x = label+'x'; vertices += left+right+[x]
    edges += [(u,v) for u in left for v in right
              if (u,v) != (left[0],right[0])]
    edges += [(left[0],x),(x,right[0]),('h',x)]
T = {u:set() for u in vertices}
for u,v in edges: T[u].add(v); T[v].add(u)
assert len(T)==22 and len(edges)==33
assert all(len(row)==3 for row in T.values())
odd_cycle = ['A0','Ax','A3','A1','A4']          # five vertices: T is not bipartite
assert all(odd_cycle[i-1] in T[odd_cycle[i]] for i in range(5))

Before Tutte: matching and parity

Throughout this lesson graphs are finite, undirected and simple: no loops or parallel edges. A matching is a set of edges with no shared vertex; a perfect matching saturates every vertex. A maximum matching has the largest possible size, written ${\alpha }^{\prime }(G)$. It need not be perfect, and a maximal matching merely forbids adding another edge without changing existing choices.

A component means a whole connected component. An odd component has an odd number of vertices, not necessarily an odd number of edges. Write $o(H)$ for the number of odd components of $H$. For a vertex set $S$, the graph $G-S$ deletes those vertices and every incident edge. Even components can be paired internally in principle; they do not contribute to $o(G-S)$. Whether such an internal pairing actually exists is a separate question.

Two earlier facts are used, and both are stated here in full for a reader who arrives without them. First, a regular bipartite graph of positive degree has a perfect matching: this is the marriage corollary of Hall's theorem, proved in module 11. Second, a connected graph in which every degree is even has an Eulerian circuit, a closed trail that uses every edge exactly once (Euler's theorem, module 04). A disconnected graph gets one circuit per component.

The naive approach and the trace of an obstruction

A computer can try every set of edges: with $m$ edges there are $2^m$ of them, and for $T$ that is $2^{33}$, about $8.6$ billion. Most are not even matchings. On a small graph the search finishes, but when it finds nothing, all it can report is "I tried everything". A reader who wants to be sure has to run the whole search again.

An obstruction is a different kind of evidence: name a set $S$, list the components of $G-S$, and count the odd ones. For $T$, take $S=\{h\}$. The component orders are $7,7,7$, so

$$o(T-S)=3>|S|=1.$$

The strict inequality matters. Equality can occur in a graph with a perfect matching; it says only that the available deleted vertices might suffice. Likewise, "many components" is not enough: an even component contributes nothing to this count.

def components_without(g,S):
    unseen = set(g)-set(S); components = []
    while unseen:
        start = next(iter(unseen)); unseen.remove(start)
        C = {start}; stack = [start]
        while stack:
            u = stack.pop()
            for v in g[u]:
                if v in unseen:
                    unseen.remove(v); C.add(v); stack.append(v)
        components.append(C)
    return components
parts = components_without(T,{'h'})
assert sorted(map(len,parts)) == [7,7,7]
assert sum(len(C)%2 for C in parts) == 3
assert 8.5e9 < 2**33 < 8.7e9

The graph need not be bipartite for this argument. It uses only the parity of component orders and the fact that a matching cannot reuse a deleted vertex. That is why it can identify obstructions beyond the setting where Hall's theorem directly applies.

Tutte's condition: necessity proved in full

Tutte's theorem. For every finite simple graph $G$, a perfect matching exists if and only if

$$o(G-S)\le |S|\text{for every }S\subseteq V(G).$$

The requirement on the right, for all sets $S$ at once, is Tutte's condition. That it is necessary is proved in full below. That it is sufficient is sketched in the next section, with the skipped lemma named.

Necessity, model write-up. Suppose $M$ is a perfect matching of $G$, and fix an arbitrary set $S\subseteq V(G)$. Consider any odd component $C$ of $G-S$. Edges of $M$ entirely within $C$ saturate an even number of its vertices. Since $|C|$ is odd, at least one vertex of $C$ is not saturated by those internal edges. It is saturated by $M$, so its matching partner lies outside $C$. That partner must belong to $S$: a neighbor outside $S$ would lie in the same component of $G-S$.

Choose one such matching edge for each odd component, and associate the component with its endpoint in $S$. Two different odd components cannot be associated with the same vertex of $S$, because $M$ uses each vertex at most once. This association is an injection from the odd components into $S$. Therefore $o(G-S)\le |S|$. As $S$ was arbitrary, the condition holds for every subset. $◻$

Proof moves used here: parity forces a vertex not paired internally; charging associates each odd component with a distinct deleted vertex; a contrapositive turns a violating set into a certificate that no perfect matching exists. The distinctness sentence is indispensable: counting components without explaining why they require separate vertices does not prove the inequality.

Sufficiency: an explicitly incomplete sketch

This section is a sketch, not a proof: two steps are used without proof, and both are named.

Suppose $G$ satisfies Tutte's condition and, for a contradiction, has no perfect matching. The order of $G$ is even: an odd order would force an odd component in $G$ itself, violating the condition at $S=\varnothing$. Now add missing edges one at a time for as long as the graph still has no perfect matching. A complete graph of even order has one, so the process stops at a graph $H$ that has no perfect matching but gains one whenever any missing edge is added.

First step used without proof. Adding an edge never increases the number of odd components left by a fixed deleted set. So $H$ still satisfies Tutte's condition. (The lab's proof-assembly exercise is this statement.)

Second step used without proof, the saturated-graph lemma. Let $U$ be the set of all vertices of $H$ that are adjacent to every other vertex. Then every component of $H-U$ is a complete graph. The usual proof supposes a component that is not complete, finds in it a path on three vertices whose ends are not adjacent, together with a missing edge at its middle vertex, takes the perfect matchings that appear when either missing edge is added, and switches edges along the cycles they form. We skip the choice of that path and both switching cases.

Granting the two steps, the rest is a construction. Let $r=o(H-U)$; Tutte's condition gives $r\le |U|$. Take one vertex from each odd component of $H-U$ and pair these $r$ vertices with $r$ different vertices of $U$, which is possible because a vertex of $U$ is adjacent to everything. What is left of every component has even order and is complete, so pair it off internally. The remaining $|U|-r$ vertices of $U$ are even in number, because $H$ has even order and everything paired so far came in twos; they are pairwise adjacent, so pair them too. That is a perfect matching of $H$, which has none. The contradiction shows that $G$ had a perfect matching after all.

Petersen's theorem on cubic graphs, stated without proof. Every finite simple 3-regular graph with no cut edge has a perfect matching. The graph $T$ shows that 3-regularity alone is not enough.

Deficiency and the parity corollary

Define the deficiency by maximizing over vertex subsets, including the empty subset:

$$def(G)={max}_{S\subseteq V(G)}(o(G-S)-|S|).$$

The number $o(G-S)-|S|$ is the surplus of $S$, so the deficiency is the largest surplus.

Berge–Tutte formula, stated without proof. For every finite simple graph $G$ of order $n$,

$${\alpha }^{\prime }(G)=\frac{n-def(G)}{2}.$$

In words: a maximum matching leaves exactly $def(G)$ vertices unsaturated. The formula contains a statement about every set and every matching, also given here without proof:

One set bounds every matching. For every vertex set $S$ and every matching $M$ of $G$, at least $o(G-S)-|S|$ vertices are unsaturated by $M$.

The necessity proof above settles the case of a perfect matching; the general case is not proved in this lesson. Every set gives a bound, and the formula adds that the best bound is attained. Neither statement says that a convenient set is the best one. Taking some $S$ and calling its surplus "the deficiency", without showing that no set does better, is a common error.

The parity fact below is proved in full. For every $S$, component orders in $G-S$ sum to $n-|S|$. Even components contribute zero modulo two and odd components contribute one. Consequently

$$o(G-S)\equiv n-|S|\left(\mathrm{mod}2\right),$$ $$o(G-S)-|S|\equiv n\left(\mathrm{mod}2\right).$$

Every possible surplus has the parity of $n$, and so does their maximum. It is nonnegative, because the empty subset gives $o(G)\ge 0$. If $n$ is even and $G$ has no perfect matching, Tutte's theorem gives some strictly positive surplus. A positive even integer is at least two, so some set satisfies

$$o(G-S)\ge |S|+2.$$

This is the parity corollary. It needs even order: when $n$ is odd, every surplus is odd, and the same argument gives only a surplus of at least one.

A small example of the formula. Let $D$ be a five-cycle together with a separate path on three vertices, eight vertices in all. With nothing deleted, its components have orders $5$ and $3$, both odd, so the empty set has surplus $2$. Trying all $2^7=128$ sets of edges shows that the largest matching has three edges. So ${\alpha }^{\prime }(D)=3$, and the formula gives $def(D)=8-2·3=2$: in this graph no set has a larger surplus than the empty set.

from itertools import combinations
D = {str(i):set() for i in range(8)}
D_edges = [('0','1'),('1','2'),('2','3'),('3','4'),('4','0'),
           ('5','6'),('6','7')]
for u,v in D_edges: D[u].add(v); D[v].add(u)
assert sorted(len(C) for C in components_without(D,set())) == [3,5]
def is_matching(F):
    ends = [v for e in F for v in e]
    return len(ends) == len(set(ends))
subsets = [F for k in range(len(D_edges)+1) for F in combinations(D_edges,k)]
largest = max(len(F) for F in subsets if is_matching(F))
assert len(subsets) == 128 and largest == 3 and len(D)-2*largest == 2

Factors: a different spanning requirement

A $k$-factor of $G$ is a spanning subgraph in which every vertex has degree $k$. Spanning means every original vertex remains, even if it receives degree zero. A 1-factor is the subgraph of a perfect matching. In a finite simple graph, a 2-factor is a disjoint union of cycles, each of length at least three, covering all vertices. Its cycles need not have even length.

Petersen's 2-factor theorem. For every integer $k\ge 1$, every finite simple $2k$-regular graph has a 2-factor. This is a different theorem from the cubic one above, and the proof below is complete. It uses the two facts recalled in "Before Tutte".

Proof. Work in each connected component. All degrees are even and positive, so an Eulerian circuit exists. Orient each edge in the direction it is traversed. Every arrival at a vertex is paired with a departure, including the circuit's closing visit. Thus indegree equals outdegree at every vertex. Their sum is $2k$, so both equal $k$.

Form a bipartite graph $B$ with two copies of every vertex: an outgoing copy $v^{+}$ and an incoming copy $v^{-}$. For each oriented edge $u\to v$, include edge $u^{+}{v}^{-}$ in $B$. Each outgoing copy has degree $k$, as does each incoming copy. By the marriage corollary of Hall, $B$ has a perfect matching $Q$.

Select in $G$ the original edges corresponding to $Q$. Every vertex has exactly one selected outgoing arc and one selected incoming arc. These cannot be the same original edge: each undirected edge was oriented in exactly one direction, and there are no loops. Nor can one original edge be selected twice, since it corresponds to just one edge of $B$. Therefore the selected undirected edges give degree two at every vertex. They form the required 2-factor. $◻$

Proof moves used here: an invariant (a closed traversal leaves every vertex as often as it enters it), decomposition into components, double counting of arrivals and departures, and a bijection between the edges of $B$ and the edges of $G$.

Here is the construction on a small graph. Take vertices $0$ to $8$ and join every two at cyclic distance one or two: eighteen edges, every degree four. The circuit that first runs $0,1,2,\dots ,8,0$ and then $0,2,4,6,8,1,3,5,7,0$ uses every edge once and orients them as $i\to i+1$ and $i\to i+2$ (modulo nine), so every vertex has two arcs in and two out. In the split graph, the edges $i^{+}(i+2{)}^{-}$ use every copy exactly once, so they form a perfect matching. The corresponding edges of the graph are drawn below: here they happen to form one cycle through all nine vertices.

arcs = [(i,(i+d)%9) for i in range(9) for d in (1,2)]
assert len({frozenset(e) for e in arcs}) == 18
assert all(sum(u==i for u,v in arcs)==sum(v==i for u,v in arcs)==2
           for i in range(9))
selected = [(i,(i+2)%9) for i in range(9)]
assert len({v for u,v in selected})==9
assert all(sum(i in e for e in selected)==2 for i in range(9))
tour = [0]
for _ in range(9): tour.append((tour[-1]+2)%9)
assert tour[-1]==0 and len(set(tour[:-1]))==9
circuit = list(range(9))+[0]+[(2*j)%9 for j in range(1,10)]
steps = list(zip(circuit,circuit[1:]))
assert circuit[0]==circuit[-1] and sorted(steps)==sorted(arcs)

What the evidence costs

Take a graph with $n$ vertices and $m$ edges, stored as adjacency lists, and count time in the usual model where a dictionary or set operation takes expected constant time. Exploring what is left after deleting a given set takes $O(n+m)$ expected time. So checking an obstruction costs $O(n+m)$: delete $S$, find the components, count the odd ones and compare with $|S|$. Checking a proposed 2-factor costs the same: every proposed edge is an edge of the graph, none is repeated, and every vertex has exactly two of them.

Finding the evidence is another matter. Trying all $2^n$ vertex sets costs $O(2^n(n+m))$ expected time, which is fine for ten vertices and hopeless for a hundred. Algorithms that find a maximum matching in a general graph in polynomial time exist, but they are not what this module teaches. What the theorems buy is on the checking side: a matching together with a set whose surplus equals the number of vertices the matching leaves unsaturated can be checked in $O(n+m)$ expected time, and by the statement "one set bounds every matching" nobody then needs to repeat the search.

For the 2-factor, the circuits and the split graph take time linear in $n+m$, and a basic augmenting-path search for the perfect matching of the split graph takes $O(n(n+m))$ expected time. Compare that with trying all $2^m$ sets of edges. The theorem promises a 2-factor, not a 2-factor with a single cycle.

A problem that looks different

A festival's map has locations and two-way routes between some of them. Every location has an even, positive number of routes, and within each connected part of the map all locations have the same number. The organizers want to keep exactly two routes at every location, so that every location lies on a closed tour; several separate tours are acceptable. Can they always do it? What would a proposed selection of routes have to show? And why would insisting on one single tour be asking for more?

Practise

In the lab you build the orientation yourself, one closed trail per frame, with the in and out counts under the drawing, and then extract a 2-factor from it. You write the search for an obstruction, assemble a proof from its steps, and find the false step in a plausible argument and the graph that refutes it. The last exercise is a problem that does not say which idea it needs; it ends with a proof you write yourself.

Recap

• You can now: check an odd-component obstruction, prove that Tutte's condition is necessary, say exactly what the sufficiency sketch leaves unproved, prove the parity corollary for even order, and prove that every $2k$-regular graph has a 2-factor.
• Invariant: a closed trail enters every vertex as often as it leaves it, so orienting a graph along closed trails keeps arcs in and arcs out equal at every vertex.
• Complexity achieved: an obstruction, a matching or a 2-factor is checked in $O(n+m)$ expected time with adjacency lists and hashing; searching all vertex sets for an obstruction costs $O(2^n(n+m))$.
• Failure mode: counting all components instead of the odd ones, or calling the surplus of one convenient set the deficiency without showing that no set does better.
• In real software: NetworkX's max_weight_matching finds matchings in general graphs with a blossom-based method, and its maxcardinality option asks for a maximum-cardinality matching.
• Retrieval: module 10 separated a maximum matching from a maximal one. Which of the two does the Berge–Tutte formula describe, and why does the other not determine a number?

Check yourself

1. In the necessity proof, why do different odd components need different vertices of $S$? Where does the proof use that the matching is perfect?
2. Name the two steps that the sufficiency sketch uses without proof.
3. State the Berge–Tutte formula. What is the difference between the surplus of a set you chose and the deficiency?
4. Prove the parity corollary for even order, and say what the same argument gives for odd order.
5. In the 2-factor proof, why can the arc kept out of a vertex and the arc kept into it not be the same edge of the graph?

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.