Hole and antihole in a graph

Question

A hole is an induced cycle of length of at least four. Its complement is called antihole. My question is: Does an antihole contain a hole of a smaller length inside? An antihole of length 5 is again a hole of length 5. Thus, it does not contain any holes of smaller length. But I noticed that a seven-vertex antihole contains a hole of length 4. What can we say about holes inside an antihole of smaller length in general? Can we determine the number of holes inside an antihole of n-vertex?

Answer 1

In general, $\overline{C_n}$ contains $\frac12n(n-3)$ induced copies of $C_4$, but no induced cycles of length $5$ or higher (unless $n=5$). It also does not contain any induced copies of $\overline{C_k}$ for $k<n$, for the same reason that $C_n$ does not contain any induced copies of $C_k$.

It is equivalent to say that $C_n$ contains $\frac12n(n-3)$ induced copies of $\overline{C_4}$, but none of $\overline{C_k}$ when $5 \le k < n$, but I'm more comfortable thinking about it from this point of view, because there's fewer edges to worry about. The argument here is:

• $\overline{C_4}$ is just two disjoint edges. We can choose an edge of $C_n$ in $n$ ways, choose an edge disjoint from it in $n-3$ ways, and to avoid double-counting we divide by $2$.
• $\overline{C_5}$ is just $C_5$, and unless $n=5$, $C_n$ does not contain $C_5$.
• $\overline{C_k}$ for $k\ge6$ is a $(k-3)$-regular graph, so $C_n$ does not have degrees big enough to contain it.