Odd Components After Vertex Deletion

What the Odd-Component Count Measures

Deleting vertices can disconnect a graph, and the resulting components need not have the same parity of order. That distinction matters when asking whether the remaining vertices can be paired by edges: a component with an odd number of vertices cannot pair all its vertices internally. The odd-component count records how many such components remain after a chosen set of vertices is removed.

Throughout, graphs are finite and simple. A connected component is a maximal connected subgraph; its order is its number of vertices. For $S\subseteq V(G)$, deleting $S$ means taking the induced subgraph on the vertices not in $S$. In particular, edges between vertices not deleted are retained.

Definition: For a graph $G$ and a vertex set $S\subseteq V(G)$, $G-S$ denotes $G[V(G)\setminus S]$. The odd-component count $o(G-S)$ is the number of connected components of $G-S$ that have odd order. The empty graph has no components, so its odd-component count is $0$.

Count components, not isolated vertices alone: an isolated vertex is an odd component of order $1$, but a larger connected component can also have odd order. Components of even order do not contribute to $o(G-S)$. The set $S$ may be empty or may equal all of $V(G)$; in the latter case $G-S$ is empty and $o(G-S)=0$.

A Parity Fact

Proposition: For every finite graph $G$ and every $S\subseteq V(G)$, $$ o(G-S)\equiv |V(G)|-|S|\pmod 2. $$

Proof. The components of $G-S$ partition its vertex set. Write their orders as $n_1,\ldots,n_k$; if $G-S$ is empty, take $k=0$. Then $$ \sum_{i=1}^{k} n_i=|V(G-S)|=|V(G)|-|S|. $$ Modulo $2$, each even $n_i$ contributes $0$, and each odd $n_i$ contributes $1$. The number of odd terms is $o(G-S)$, so the sum is congruent to $o(G-S)$ modulo $2$. If $k=0$, both sides are $0$, so the same calculation includes the empty graph. $\square$

This proposition is a parity check on a calculation, not a way to determine the count by itself. For example, if six vertices remain, the number of odd components must be even, but it could be $0$, $2$, $4$, or $6$, depending on how those vertices are connected.

Proposition: If a graph is a disjoint union of graphs $H_1,\ldots,H_r$, then its odd-component count is the sum of the odd-component counts of those graphs. This holds as well when some $H_i$ is empty.

Proof. A disjoint union has no edges between the vertex sets of its constituent graphs. Therefore each connected component of the union is a connected component of exactly one $H_i$, and every component of every $H_i$ occurs in the union. Its order is unchanged. Counting the components of odd order in the union consequently counts the odd-order components of each $H_i$ once, giving the stated sum. An empty graph contributes no components and hence contributes $0$. $\square$

Calculating the Count

Worked Example: Deleting Two Vertices from a Path

Let $G$ have $V(G)=\{1,2,3,4,5,6,7\}$ and $E(G)=\{12,23,34,45,56,67\}$, so $G$ is the path $P_7$. Calculate $o(G-S)$ for $S=\{3,5\}$.

After deleting $3$ and $5$, the remaining vertex set is $\{1,2,4,6,7\}$. The retained edges are $12$ and $67$. Thus the components are $\{1,2\}$, $\{4\}$, and $\{6,7\}$, of orders $2,1,2$, respectively. Only the middle component has odd order, so $o(G-S)=1$.

Check: The remaining order is $7-2=5$, which is odd. The count $1$ is odd as required by the parity proposition. There are three components altogether, but only one is odd.

Worked Example: One Deleted Vertex Leaves Three Odd Components

Let $G$ have $V(G)=\{x,a,b,c,d,e\}$ and $E(G)=\{xa,xb,xc,cd,de\}$. Take $S=\{x\}$. After deletion, the components are the isolated vertices $\{a\}$ and $\{b\}$, and the path on $\{c,d,e\}$. Their orders are $1,1,3$, so all three are odd and $o(G-S)=3$.

Why this signals a matching obstacle. A matching is a set of edges with no shared endpoints; it is perfect if every vertex is incident with one of its edges. In a perfect matching of this graph, each of the three odd components left after deleting $x$ would need at least one matching edge joining it to a vertex outside that component. Indeed, edges within a component cover an even number of its vertices, so an odd number of vertices cannot all be covered using only internal edges. The only possible outside vertex for these components is $x$. Matching edges incident with distinct components would require distinct vertices of $S$, but $S$ contains just $x$. It cannot serve all three components, so this graph has no perfect matching.

Check: The graph has $6$ vertices, an even number, so parity alone does not rule out a perfect matching. But $o(G-S)=3$ is greater than $|S|=1$, and the component-by-component argument shows why the deletion creates the obstruction.

Worked Example: Two Odd Components Can Be Matched Across the Deleted Set

Let $G$ be the cycle with $V(G)=\{1,2,3,4,5,6,7,8\}$ and $E(G)=\{12,23,34,45,56,67,78,81\}$. Delete $S=\{2,6\}$. The remaining vertices are $\{1,3,4,5,7,8\}$, and the retained edges are $34,45,78,81$. The components are the path $3,4,5$ and the path $7,8,1$, each of order $3$. Therefore $o(G-S)=2$.

Check: There are $8-2=6$ remaining vertices, and the count $2$ is even. In this case, the two odd components do not prevent a perfect matching of the original graph: its edges $12,34,56,78$ form one. Vertices $2$ and $6$ match to vertices in the two different odd components, while the remaining vertices pair internally.

Reading the Count Carefully

When computing $o(G-S)$, the reliable procedure is to identify the remaining vertices, find every component using the retained edges, determine each component's order, and count only the odd orders. The parity proposition then supplies a quick consistency check.

A useful distinction is between the number of components and the number of odd components. In the first worked example, deleting two vertices leaves three components, but only one has odd order. Calling the answer $3$ would confuse the total component count with $o(G-S)$.

Odd components help explain why deletion can obstruct a perfect matching, but their presence alone does not establish an obstruction. The cycle example has two odd components after deleting two vertices, yet the original graph has a perfect matching. The locations of edges to the deleted vertices matter: a deleted vertex can be matched to a vertex in one of the odd components. The next step in studying perfect matchings is to test this issue across all choices of $S$, rather than drawing a conclusion from a single deletion.

There is also a useful boundary check. If $S=V(G)$, then $G-S$ is empty and $o(G-S)=0$; there is no component to count. If $S=\varnothing$, then $o(G-S)$ simply counts the odd-order components of $G$ itself. The parity proposition covers both cases without modification.

Common Pitfall

Suppose the graph and deleted set are as in the first worked example. The components of $G-S$ have orders $2,1,2$. A wrong calculation reports $o(G-S)=3$, because there are three components. The correction is to test each order for oddness: $2$ is even, $1$ is odd, and $2$ is even. Exactly one component qualifies, so $o(G-S)=1$. As a further check, $G-S$ has $5$ vertices, and an odd count agrees with the parity proposition.

Check Your Understanding

For each calculation, list the components of the remaining graph and their orders before giving the odd-component count.

Let $G$ have vertices $\{1,2,3,4,5,6\}$ and edges $\{12,23,34,45,56\}$. Find $o(G-\{3\})$ and check its parity.
Let $G$ have vertices $\{a,b,c,d,e,f\}$ and edges $\{ab,bc,cd,de,ef,fa\}$. Find $o(G-\{b,e\})$.
Why is the odd-component count of the empty graph $0$, and how does that fit the parity proposition when $S=V(G)$?
For the path in Question 1, how many components remain after deleting $3$, and how many of them have odd order?
In the second worked example, explain why the three odd components after deleting $x$ cannot all be covered by matching edges to $x$.