Odd Components, Tight Sets and Barriers
Deleting vertices can split a graph into components, some of which have odd order. These odd components matter for matchings: an odd component cannot have all its vertices paired by edges entirely within that component. Vertices deleted to form the components may provide partners, but each deleted vertex can serve at most one component. Tight sets and barriers formalize this counting constraint.
All graphs in this tutorial are finite and simple. For \(S\subseteq V(G)\), \(G-S\) is the induced subgraph on \(V(G)\setminus S\). A component is a maximal connected subgraph, and its order is its number of vertices. Write \(o(G-S)\) for the number of components of \(G-S\) having odd order. In particular, the graph with no vertices has zero components, so \(o(G-\varnothing)=0\) when \(G\) itself is empty.
The maximum exists because a finite graph has finitely many vertex subsets. Also, \(\operatorname{def}_T(G)\geq 0\): taking \(S=V(G)\) gives \(G-S\) empty and \(q_G(S)=-|V(G)|\), while taking \(S=\varnothing\) gives \(q_G(\varnothing)=o(G)\geq0\). Thus a tight set is a barrier precisely when the maximum Tutte value is zero. If the maximum is positive, tight sets can still exist, but they do not attain it.
Why These Sets Constrain Matchings
A matching is a set of edges no two of which share a vertex. A vertex is unmatched by a matching if it is not an endpoint of any edge in it. For any matching \(M\), any vertex set \(S\), and any odd component \(C\) of \(G-S\), there are two possibilities. Either \(C\) contains an unmatched vertex, or an edge of \(M\) joins a vertex of \(C\) to a vertex of \(S\). Indeed, if every vertex of \(C\) is matched and all its matching edges stay inside \(C\), those edges would cover an even number of vertices, contrary to \(|V(C)|\) being odd.
Proof. Let \(u\) be the number of vertices unmatched by \(M\). Consider the odd components of \(G-S\). Every such component that has no unmatched vertex must have a matching edge to \(S\), by the parity argument above. Distinct components require distinct vertices of \(S\): a vertex of \(S\) can be incident with only one edge of the matching, and an edge from \(S\) can enter only one component of \(G-S\). Therefore at most \(|S|\) odd components can have no unmatched vertex. At least \(o(G-S)-|S|\) odd components each contain an unmatched vertex, and these vertices are distinct because the components are disjoint. Hence \(u\geq o(G-S)-|S|=q_G(S)\). This holds for every \(S\), so \(u\) is at least the maximum of these values, namely \(\operatorname{def}_T(G)\). \(\square\)
Since a matching of size \(|M|\) leaves exactly \(|V(G)|-2|M|\) vertices unmatched, the theorem also gives \(|V(G)|-2|M|\geq\operatorname{def}_T(G)\). A barrier is therefore a set that witnesses the strongest bound obtainable from these odd-component counts. This is a necessary bound on matchings; by itself it does not assert that any matching attains the bound.
Computing Tight Sets and Barriers
Worked Example: A Path with a Perfect Matching
Let \(G\) have \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,23,34\}\), the path \(P_4\). We compute \(q_G(S)\) by the size of \(S\).
For \(S=\varnothing\), the graph is connected of order \(4\), so \(o(G-S)=0\) and \(q_G(S)=0-0=0\). For a singleton \(S=\{i\}\), deleting any one vertex leaves exactly one odd component: deleting an endpoint leaves a path on three vertices, while deleting an internal vertex leaves one isolated vertex and one component of order two. Thus for each of the four singleton sets, \(q_G(S)=1-1=0\).
For two-element sets, the six possibilities give the following counts. Removing \(\{1,2\}\) leaves the edge \(34\), so \(q=0-2=-2\). Removing \(\{1,3\}\) leaves isolated vertices \(2,4\), so \(q=2-2=0\). Removing \(\{1,4\}\) leaves the edge \(23\), so \(q=0-2=-2\). Removing \(\{2,3\}\) leaves isolated vertices \(1,4\), so \(q=2-2=0\). Removing \(\{2,4\}\) leaves isolated vertices \(1,3\), so \(q=2-2=0\). Removing \(\{3,4\}\) leaves the edge \(12\), so \(q=0-2=-2\).
If \(|S|=3\), one vertex remains and is an odd component, giving \(q=1-3=-2\). If \(|S|=4\), no vertices remain, giving \(q=0-4=-4\). These cases cover every subset. The maximum is \(0\); hence the tight sets are exactly \(\varnothing\), all four singletons, and \(\{1,3\},\{2,3\},\{2,4\}\). All of them are barriers.
Check: the matching \(\{12,34\}\) covers all four vertices. For each barrier found above, the theorem gives the lower bound \(0\) unmatched vertices, consistent with this matching. In particular, the empty set has \(o(G)=0\), so its Tutte value is \(0\), confirming that the maximum cannot be negative.
Worked Example: A Barrier with Positive Tutte Deficiency
Let \(G\) have \(V(G)=\{c,a,b,d\}\) and \(E(G)=\{ca,cb,cd\}\), the star \(K_{1,3}\). For \(S=\varnothing\), the graph is one component of order four, so \(q_G(S)=0\). If \(S\) is a singleton leaf, the remaining graph is connected of order three, so \(q_G(S)=1-1=0\). If \(S=\{c\}\), the remaining vertices \(a,b,d\) are three isolated odd components, so \(q_G(S)=3-1=2\).
For a two-element set containing \(c\), the remaining two vertices are isolated leaves. There are two odd components, so \(q=2-2=0\). For a two-element set consisting of leaves, the remaining graph is an edge from \(c\) to the one remaining leaf; it has no odd components, so \(q=0-2=-2\). If \(|S|=3\), exactly one vertex remains, giving \(q=1-3=-2\); if \(|S|=4\), then \(q=0-4=-4\). Thus the maximum is \(2\), attained by \(\{c\}\), and this is the unique barrier. The tight sets are the empty set, each singleton leaf, and each two-element set containing \(c\).
This graph shows why “tight” and “barrier” are different terms: the tight sets have value \(0\), while the maximum value is \(2\). The matching \(\{ca\}\) leaves \(b,d\) unmatched. In fact, any matching uses at most one edge, because every edge is incident with \(c\), so every matching leaves at least two vertices unmatched. The barrier \(\{c\}\) certifies this: its three odd components can be connected to at most one vertex of the set by matching edges, leaving at least \(3-1=2\) odd components with unmatched vertices.
Check: the four edges \(ca,cb,cd\) are all incident with \(c\), so a matching contains at most one of them and has at most one edge. The matching \(\{ca\}\) has one edge and leaves \(4-2(1)=2\) vertices unmatched, agreeing with the barrier bound \(2\).
Worked Example: An Empty Set That Is a Barrier
Let \(G\) have \(V(G)=\{a,b,c,x\}\) and \(E(G)=\{ab,bc,ca\}\). This graph consists of a triangle and an isolated vertex. For \(S=\varnothing\), there are two odd components, the triangle and the isolated vertex, so \(q_G(\varnothing)=2-0=2\).
If \(S\) is any singleton, deleting the isolated vertex leaves the triangle, which contributes one odd component; the value is \(1-1=0\). Deleting a triangle vertex leaves an edge and the isolated vertex, again one odd component and value \(1-1=0\). For any \(S\) with \(|S|\geq2\), the graph \(G-S\) has at most \(4-|S|\) components, so \(o(G-S)\leq4-|S|\). It follows that \(q_G(S)\leq4-2|S|\leq0\). Therefore the maximum is \(2\), attained only by \(S=\varnothing\), which is a barrier.
A matching can use at most one triangle edge, and the isolated vertex cannot be matched at all. For example, \(\{ab\}\) leaves \(c\) and \(x\) unmatched. The empty-set barrier records the two odd components already present before any deletion.
Check: \(\{ab\}\) has one edge, so it leaves \(4-2(1)=2\) vertices unmatched, exactly the lower bound \(\operatorname{def}_T(G)=2\).
Tight Sets in Graphs with Perfect Matchings
A useful special case explains why tight sets arise naturally when studying perfect matchings. A perfect matching covers every vertex. If a graph has a perfect matching, every component has even order: matching edges cannot join distinct components, and within each component they cover vertices in pairs.
Proof. Let \(M\) be a perfect matching. The matching bound proved above says that for every \(S\subseteq V(G)\), the number of unmatched vertices, which is zero, is at least \(q_G(S)\). Thus \(q_G(S)\leq0\) for every \(S\). Taking \(S=\varnothing\), every component of \(G\) has even order by the pairings in \(M\), so \(o(G)=0\) and \(q_G(\varnothing)=0\). The maximum of all the values is therefore exactly \(0\). A set is a barrier precisely when its value equals this maximum, which here means exactly \(q_G(S)=0\), the definition of tightness. \(\square\)
This proposition gives a necessary perspective, not a converse: it does not say that a graph with maximum Tutte value zero must have a perfect matching. The condition on all vertex sets is an important matching criterion, but its sufficiency is established separately in the development of Tutte’s theorem.
Common Pitfall: Counting the Wrong Quantity
Do not count vertices of \(G-S\) or all of its components in place of its odd components. For the star example with \(S=\{c\}\), \(G-S\) has three vertices and three components, all odd, so \(o(G-S)=3\) and the Tutte value is \(3-1=2\). A common incorrect calculation is \(o(G-S)+|S|=3+1=4\), or counting the three remaining vertices and then subtracting nothing. Both miss the definition: subtract the size of the deleted set exactly once.
Also distinguish the role of a tight set from that of a barrier. Tightness asks whether the value is zero; being a barrier asks whether the value is as large as possible. In the star, a singleton leaf is tight but not a barrier, because the center has value \(2\). In a graph with a perfect matching, the maximum value is zero, so the two notions do coincide.
Check Your Understanding
Use \(q_G(S)=o(G-S)-|S|\) in each question, and distinguish a zero value from a maximum value.
- For the path on vertices \(\{1,2,3\}\) with edges \(\{12,23\}\), compute \(q_G(S)\) for \(S=\varnothing\), \(\{2\}\), and \(\{1,3\}\). Which of these are tight?
- In the graph with vertices \(\{a,b,c,d\}\) and edges \(\{ab,bc,cd,da\}\), show that the empty set is tight. Does the proposition imply it is a barrier?
- Explain why distinct odd components of \(G-S\) that are fully matched must use distinct vertices of \(S\).
- A graph has Tutte deficiency \(3\). What lower bound does this give on the number of unmatched vertices in every matching?
- Give an example from this tutorial of a tight set that is not a barrier, and compute both its Tutte value and the graph’s maximum value.