1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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}$.

$\endgroup$
1
  • $\begingroup$ Wonderfully simple, thank-you! $\endgroup$ Jun 13 at 20:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.