Bounding the Number of Vertices Lost to Short Cycles

From Short Cycles to a Vertex Bound

A graph with no short cycles can be useful, but a random graph usually contains some. The alteration idea is to find a random graph with few cycles of the lengths we want to exclude, then delete vertices to destroy those cycles. The key quantity is the number of short cycles: deleting one vertex from each such cycle is enough, and the number of distinct vertices deleted can only be smaller than the number of cycles counted.

Throughout, graphs are finite and simple. Fix an integer $g\ge3$. A short cycle here means a cycle whose length is between $3$ and $g$, inclusive. For an integer $n\ge1$ and $0\le p\le1$, the Bernoulli random graph $G(n,p)$ has vertex set $V=\{1,\dots,n\}$; each of the $\binom n2$ possible edges is included independently with probability $p$. Thus each outcome is a graph $H=(V,E)$, where $E$ is a random subset of the possible edges.

Definition: Let $X_g$ be the number of cycles in $G(n,p)$ whose lengths are at most $g$. Let $L_g$ denote the number of vertices deleted by a chosen deletion procedure that destroys every such cycle. The basic bound will be $L_g\le X_g$.

If $g>n$, no cycle can have length greater than $n$, so all sums over cycle lengths stop at $\min(g,n)$. When $n<3$, there are no cycles and $X_g=0$. The estimates below include this case by interpreting a sum with no terms as zero.

Expected Number of Short Cycles

Proposition: For $G(n,p)$, the expected number of cycles of length at most $g$ is $$ \mu_g=\mathbb{E}[X_g]=\sum_{\ell=3}^{\min(g,n)}\frac{(n)_\ell}{2\ell}p^\ell, $$ where $(n)_\ell=n(n-1)\cdots(n-\ell+1)$.

Proof. Fix a length $\ell$ with $3\le\ell\le n$. An ordered list of $\ell$ distinct vertices specifies a cycle by joining consecutive vertices and joining the last to the first. Each undirected cycle is represented $2\ell$ times in these lists: there are $\ell$ choices of starting vertex and two directions around the cycle. There are $(n)_\ell$ ordered lists, so the number of possible cycles of length $\ell$ is $(n)_\ell/(2\ell)$.

For each possible cycle $C$, let $I_C=1$ if all its $\ell$ edges are present and $I_C=0$ otherwise. Independence of edge choices gives $\mathbb{E}[I_C]=\Pr(I_C=1)=p^\ell$. The number of cycles of length $\ell$ in the random graph is the sum of these indicators, so linearity of expectation gives expected count $(n)_\ell p^\ell/(2\ell)$. Summing over the allowed lengths proves the formula. If there are no allowed lengths, both the random count and the empty sum are zero. $\square$

The formula counts expected cycles, not the probability that at least one cycle occurs. It does not require different cycles to use disjoint edges or vertices: linearity of expectation applies even when the indicators are dependent.

Deleting Vertices and Bounding the Loss

Theorem: For any realized graph $H$, if it contains $X_g(H)$ cycles of length at most $g$, there is a set $S\subseteq V(H)$ with $|S|\le X_g(H)$ such that the induced subgraph $H[V(H)\setminus S]$ has no cycle of length at most $g$. Consequently, in $G(n,p)$ there is an outcome for which at most $\lfloor\mu_g\rfloor$ vertices need to be deleted to eliminate all cycles of length at most $g$.

Proof. List the short cycles in $H$ as $C_1,\dots,C_x$, where $x=X_g(H)$. If $x=0$, take $S=\varnothing$; the claim holds. Otherwise, choose one vertex $v_i$ from each $C_i$, and let $S=\{v_1,\dots,v_x\}$. Repeated choices can give the same vertex, so $|S|\le x$. Every short cycle of $H$ is on the list and contains its chosen vertex. It therefore loses at least one vertex when $S$ is deleted. A cycle in the induced subgraph would also be a cycle of $H$, so no short cycle remains.

For the probabilistic claim, $X_g$ is a nonnegative integer-valued random variable on a finite probability space and has mean $\mu_g$. At least one outcome has $X_g\le\mu_g$; otherwise every outcome would have value strictly greater than $\mu_g$, forcing their weighted average to be greater than $\mu_g$. Since $X_g$ is an integer, that outcome has $X_g\le\lfloor\mu_g\rfloor$. Apply the deletion argument to it. $\square$

When $\mu_g<1$, the integer-valued count has an outcome equal to zero, so no deletions are needed in that outcome. More generally, the floor in the theorem is useful when $\mu_g$ is not an integer. If the resulting bound is at least $n$, it remains correct but may give no useful information about the number of vertices left.

Probability bound: If $X\ge0$ and $a>0$, then $\Pr(X\ge a)\le\mathbb{E}[X]/a$. In particular, if $\mu_g>0$, then $\Pr(X_g<2\mu_g)\ge\frac12$.

Proof. On the event $X\ge a$, the value of $X$ is at least $a$; off that event, $X$ is nonnegative. Therefore $\mathbb{E}[X]\ge a\Pr(X\ge a)$, which gives the stated inequality after division by $a$. Taking $X=X_g$ and $a=2\mu_g>0$ gives $\Pr(X_g\ge2\mu_g)\le\frac12$. Its complementary event is $X_g<2\mu_g$, proving the claim. $\square$

The strict inequality matters: the complement of $X_g\ge2\mu_g$ is $X_g<2\mu_g$. This gives a probability guarantee for a random outcome, while the expectation argument gives at least one outcome with $X_g\le\mu_g$. These are different forms of information.

Worked Example: A Triangle-Free Outcome on Twelve Vertices

Take $G(12,\frac14)$, with $V=\{1,\dots,12\}$ and each possible edge included independently with probability $\frac14$. Set $g=3$, so $X_3$ counts triangles only. There are $\binom{12}{3}=220$ possible triangles, and each requires three specified edges, so its probability of appearing is $(\frac14)^3=\frac1{64}$. Hence $$ \mu_3=220\cdot\frac1{64}=\frac{55}{16}=3.4375. $$

The expectation theorem guarantees an outcome with $X_3\le\lfloor55/16\rfloor=3$. Deleting one vertex from each triangle deletes at most three vertices, leaving at least $12-3=9$ vertices and no triangle.

Check: If every outcome had at least four triangles, the expected count would be at least $4$, but $\frac{55}{16}<4$. Thus an outcome with at most three triangles must exist. The cycle count used above is also obtained directly by choosing three vertices: every three-vertex set supports exactly one possible triangle.

Worked Example: A Positive Probability of No Short Cycles

Take $G(10,\frac1{10})$, with $V=\{1,\dots,10\}$, and set $g=4$. There are $\binom{10}{3}=120$ possible triangles, each present with probability $(\frac1{10})^3=\frac1{1000}$. Their expected count is $120/1000$.

For 4-cycles, first choose four vertices in $\binom{10}{4}=210$ ways. On each chosen set there are three distinct undirected 4-cycles: among the six possible edges on four vertices, each cycle is determined by its two diagonals being absent, giving three choices of diagonal pair. Each specified cycle requires four edges, so its probability is $(\frac1{10})^4=\frac1{10000}$. The expected number of 4-cycles is therefore $3\cdot210/10000=630/10000$. Adding the two lengths gives $$ \mu_4=\frac{120}{1000}+\frac{630}{10000} =\frac{1200+630}{10000} =\frac{183}{1000}. $$

Because $X_4$ is a nonnegative integer, $\Pr(X_4\ge1)\le\mathbb{E}[X_4]=183/1000$, using the probability bound with $a=1$. Thus $$ \Pr(X_4=0)\ge1-\frac{183}{1000}=\frac{817}{1000}. $$

So with probability at least $817/1000$, this random graph already has no cycle of length $3$ or $4$, and no vertex deletion is required. Check: the two expected counts add to $1200/10000+630/10000=1830/10000=183/1000$, as calculated.

Worked Example: Overlapping Cycles Can Cost Fewer Vertices

Let $H=(V,E)$ have $V=\{1,2,3,4,5\}$ and $E=\{12,23,13,34,14\}$. For $g=3$, the triangles are $1,2,3,1$ and $1,3,4,1$. These are the only triangles: vertex $5$ is isolated, and the listed edges on $\{1,2,3,4\}$ contain no other three-edge triangle.

There are $X_3(H)=2$ short cycles. Choose vertex $3$ from each; the chosen set is $S=\{3\}$, so only one vertex is deleted. The remaining vertex set is $\{1,2,4,5\}$, and the remaining edges are $12$ and $14$. This graph has no triangle, so the deletion succeeds with $|S|=1\le2=X_3(H)$.

Check: both original triangles contain $3$, and deleting $3$ removes the edges $23,13,34$. The two edges that remain cannot form a cycle. The number of deleted vertices can be strictly smaller than the number of short cycles when cycles overlap.

Choosing the Edge Probability

Corollary: Fix an integer $g\ge3$. For $n\ge2$, set $p=n^{-g/(g+1)}$. There is an outcome of $G(n,p)$ from which at most $$ \frac{g-2}{6}\,n^{g/(g+1)} $$ vertices need be deleted to eliminate every cycle of length at most $g$. In particular, for fixed $g$, this bound is $o(n)$ as $n$ grows.

Proof. Put $q=np=n^{1/(g+1)}$, so $q\ge1$. For each allowed length $\ell$, the cycle-count formula and $(n)_\ell\le n^\ell$ give an expected contribution at most $q^\ell/(2\ell)$. Since $\ell\ge3$, $2\ell\ge6$; since $q\ge1$ and $\ell\le g$, $q^\ell\le q^g$. There are at most $g-2$ lengths from $3$ through $g$. Consequently, $$ \mu_g\le\frac{g-2}{6}q^g =\frac{g-2}{6}n^{g/(g+1)}. $$

The expectation theorem gives an outcome with at most $\mu_g$ short cycles, and deleting one vertex per cycle loses no more than that many vertices. Finally, for fixed $g$, dividing the bound by $n$ gives at most $\frac{g-2}{6}n^{-1/(g+1)}$, which tends to zero as $n$ grows. Thus the number deleted is $o(n)$. $\square$

This estimate identifies how the short-cycle count changes with $p$: a cycle of length $\ell$ contributes a factor of roughly $(np)^\ell$ to its expected count. Choosing $p$ so that the longest excluded cycles have expected count below linear order makes the deletion loss a vanishing fraction of the $n$ vertices. The corollary controls the number of vertices lost; it does not, by itself, assert any additional property of the graph after deletion.

Common Pitfall

Do not count ordered descriptions as distinct cycles. For $n=6$, there are $6\cdot5\cdot4=120$ ordered lists of three distinct vertices. A mistaken calculation might call these 120 different triangles and, at $p=\frac12$, report expected triangle count $120\cdot\frac18=15$. But each undirected triangle is counted $3\cdot2=6$ times, once for each starting vertex and direction. There are $120/6=20$ distinct possible triangles, so the correct expectation is $20\cdot\frac18=\frac52$. This also follows from $\binom63=20$, since each three-vertex set supports one possible triangle.

Do not assume each cycle costs a different vertex. The deletion argument chooses one vertex from every original short cycle, then deletes the set of chosen vertices. Overlap can make that set smaller than the cycle count, as in the example with two triangles sharing an edge. The guaranteed upper bound is the number of cycles, not an assertion that the number of distinct deletions equals it.

Check Your Understanding

Use the cycle-count formula and the deletion bound to answer these questions.

In $G(9,\frac13)$, what is the expected number of triangles? State the number of possible triangles and the probability that any fixed one appears.
For $G(8,\frac12)$ with $g=4$, write the expected-count formula for triangles and 4-cycles. How many undirected 4-cycles are possible on a fixed set of four vertices?
Explain why a graph with $x$ cycles of length at most $g$ can be made free of those cycles by deleting at most $x$ vertices, including the case $x=0$.
If $\mathbb{E}[X_g]=\frac25$, what lower bound does Markov’s inequality give for $\Pr(X_g=0)$?
For fixed $g$, why does the deletion bound in the corollary represent a vanishing fraction of the original $n$ vertices?