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