Vertex Deletion to Raise Girth

From Short Cycles to Vertex Deletion

A graph with no short cycles can be useful in constructions, but a graph that has a few short cycles may be easier to obtain. The alteration step is simple: choose vertices so that every short cycle loses at least one of its vertices, then keep the induced subgraph on the vertices left over. The key point is that this operation cannot create a cycle. It can only preserve cycles that were already present and whose vertices were all retained.

Throughout, graphs are finite and simple. Let \(g\ge 3\) be an integer. A cycle has length equal to its number of edges. The girth of a graph containing a cycle is the length of its shortest cycle; an acyclic graph, including the empty graph, is assigned girth infinity. Thus girth greater than \(g\) means that there is no cycle of length at most \(g\).

There are finitely many cycles in a finite graph. Let \(C_g(G)\) denote the number of distinct cycles of length at most \(g\), counting a cycle once regardless of its starting point or direction. A direct procedure scans those cycles and selects a vertex from each cycle that has not already been hit. The selected vertices are deleted together at the end. Selecting a vertex can hit several cycles at once, so the number of distinct vertices selected can be smaller than the number of short cycles.

The Deletion Guarantee

Proof. List all \(C_g(G)\) short cycles. Start with \(D=\varnothing\). Scan the list in any order. When a cycle already meets \(D\), make no change. When it does not meet \(D\), add one of its vertices to \(D\). Each cycle causes at most one addition, so after the scan \(|D|\le C_g(G)\). Every short cycle in the list meets the final \(D\): it either met \(D\) when it was scanned, and remains hit because \(D\) only grows, or a vertex of it was added at that step.

Set \(H=G[V(G)\setminus D]\). If \(H\) had a cycle of length at most \(g\), that cycle would also be a cycle of \(G\), since \(H\) is induced. It would therefore be on the scanned list. But all its vertices lie outside \(D\), contradicting that every listed cycle is hit. Hence \(H\) has girth greater than \(g\). Finally, \(|V(H)|=|V(G)|-|D|\ge |V(G)|-C_g(G)\). If \(C_g(G)=0\), the procedure selects nothing and the same argument says \(G\) already has girth greater than \(g\). \(\square\)

The guarantee is a construction, not a claim that the deletion set is smallest. The scan makes a valid set even if it does not find the best one. In particular, it is the number of distinct selected vertices that controls the number retained; cycles sharing a vertex may all be hit by one deletion.

Minimum Deletion and Cycle Hitting

The same idea gives an exact description of the smallest possible deletion set. Define \(\mu_g(G)\) to be the minimum size of a set \(D\subseteq V(G)\) for which \(G[V(G)\setminus D]\) has girth greater than \(g\). Such a set exists: deleting all vertices always leaves the empty graph, which is acyclic. A set meeting every short cycle is often called a hitting set for those cycles.

Proof. Suppose first that \(D\) hits every cycle of length at most \(g\). Any cycle in \(G[V(G)\setminus D]\) would also be a cycle of \(G\), and none of its vertices would lie in \(D\). If its length were at most \(g\), this would contradict the assumption that \(D\) hits every such cycle. Therefore the remaining induced subgraph has girth greater than \(g\).

Conversely, suppose \(G[V(G)\setminus D]\) has girth greater than \(g\). If some cycle of \(G\) of length at most \(g\) were disjoint from \(D\), all of its vertices would remain. Because the subgraph is induced, all the cycle’s edges would remain too, giving a cycle of length at most \(g\) in \(G[V(G)\setminus D]\). This contradicts its girth. Thus \(D\) hits every short cycle. The two conditions describe exactly the same sets \(D\), so their minimum sizes are equal. This also covers the case of no short cycles: the empty set hits them all, and no deletion is needed. \(\square\)

Using the Guarantee in an Existence Argument

The deletion step is useful when a graph is already known to have few short cycles. If \(G\) has \(n\) vertices and \(C_g(G)<n\), the theorem leaves at least \(n-C_g(G)>0\) vertices in a graph of girth greater than \(g\). More generally, whenever a particular graph has \(C_g(G)\le n-k\), the construction leaves at least \(k\) vertices. These statements use the actual number of short cycles in that graph; they do not require the scan to find a minimum hitting set.

There is also a basic probabilistic consequence. Suppose a random graph has a fixed order \(n\), and let \(X\) be its number of cycles of length at most \(g\). If its expected number satisfies \(\mathbb{E}[X]<n\), then some outcome has \(X<n\). Indeed, if every outcome had \(X\ge n\), its expectation would be at least \(n\). Apply the deletion procedure to that outcome: it leaves at least \(n-X>0\) vertices and no cycle of length at most \(g\). The probabilistic input supplies an outcome with few short cycles; vertex deletion converts that outcome into one with larger girth.

Common Pitfall: Count Distinct Deleted Vertices

In the first example there are two triangles, but both contain vertex \(3\). Saying “there are two short cycles, so delete two vertices” confuses the number of cycles with the number of distinct selected vertices. The scan chooses \(3\) for the first triangle, and the second is already hit. Thus \(D=\{3\}\) has size \(1\), not \(2\), and four vertices remain rather than three.

A different mistake is to delete one edge from each short cycle and call the result a vertex-deletion construction. Edge deletion may break cycles, but it does not produce the induced subgraph obtained by removing vertices. Here the method specifically chooses vertices and removes every incident edge along with them. Checking that the remaining graph is induced is part of verifying that the stated construction has been carried out.