# If every $k$-vertex induced subgraph of $G$ has $m$ edges, then $G$ is either complete or empty.

Let $$e(G)$$ be the number of edges in $$G$$. I've been trying the following exercise from Doug West's Graph Theory, and would like an answer for part (b):

13.26) Suppose $$n, k \in \mathbb{Z}$$ satisfy $$1 < k < n-1$$ and $$n\geq 4$$. Suppose $$G$$ is a simple $$n$$-vertex graph and that every $$k$$-vertex induced subgraph of $$G$$ has $$m$$ edges.

a) Suppose $$G'$$ is an induced subgraph of $$G$$ with $$j$$ vertices, where $$j>k$$. Prove that $$e(G') = m\cdot \binom{j}{k}\cdot \frac{1}{\binom{j-2}{k-2}}$$

b) Use (a) to prove that $$G=K_n$$ or $$G=\overline{K_n}$$. Hint: use (a) to compute the entry in the adjacency matrix for the vertex pair $$uv$$; the formula is independent of the choice of $$u$$ and $$v$$.

Part (a) is pretty simple. Count the number of pairs $$(e, H)$$ where $$H$$ is an induced $$k$$-vertex subgraph of $$G$$ and $$e$$ is an edge of $$G$$. Then divide by the number of ways to make $$H$$ for a given edge $$e$$.

But part (b) I have no idea. I'd prefer an answer that makes use of the hint.

## 1 Answer

Take $$G'$$ to be any subset of vertices of size $$k+2$$ containing $$u$$ and $$v$$ (note that $$k+2\le n$$, so it exists). Then you can check that by inclusion-exclusion,

$$A_{uv}=e(G')-e(G'\setminus{u})-e(G'\setminus{v})+e(G'\setminus\{u,v\}).$$

From question (a) for $$j=k+1,k+2$$ and the hypothesis for $$j=k$$, it follows that $$A_{uv}$$ does not depend on $$(u,v)$$. From there you can conclude that $$G=K_n$$ or $$G=\bar{K_n}$$.

• Wonderfully simple, thank-you! Jun 13 at 20:51