Graph Theory with Applications (Bondy, Murty)
Exercise $1.4.5^*$
Let $G$ be simple and $n$ be an integer such that $1\lt n\lt\nu-1$. Show that if $\nu\geq4$ and all induced subgraphs of $G$ on $n$ vertices have the same number of edges, then either $G\cong K_\nu$ or $G\cong K_\nu^c$.
$G$ is a simple graph with $\nu$ vertices, $K_\nu$ is the complete graph on $\nu$ vertices.
There is a similar question here, but the solution assumes that the condition is true for all values of $n$ instead of just a specific one.
Here is my attempt.
An induced subraph with $n$ vertices has $k$ edges, say. Take a set $V'\subseteq V$ with $n-1$ vertices. Take some $u,v\not\in V'$, which is possible as $n<\nu-1$ so $n+1\lt\nu$. Then $G[V'+u]$ and $G[V'+v]$ have $k$ edges. So the number of edges between $V'$ and $u$ is the same as the number of edges between $V'$ and $v$. This is true for any set $V'$ with $u,v$ fixed, so adding over all such sets and dividing by $\nu-2\choose n-1$ we see that $d(u)=d(v)$. This is true for all $u,v$, so $G$ is regular.
Now take some vertex $v\in V$. If its degree is zero, then $G=K_\nu^c$. Suppose its degree is nonzero. Let it be $d$. Take the set of $v$ and its adjacent vertices, being a set of $d+1$ vertices.
But now I can't see where to go. Please help.
Best Answer
Using contradiction, we assume that there exist vertices $a$ and $b$ that are connected; the vertices $c$ and $d$ are not connected. As for any $2 \leq n \leq v-2$, we can always find a set of vertices $X$ having $n-2$ vertices and all the vertices are different from $a,b,c,d$.
Denote $A,B,C,D$ the number of edges that $a,b,c,d$ are adjacent to all the vertices in $X$, respectively. Denote $S$ the number of edges that vertices in $S$ are adjacent to each other.
Now consider the induced subgraphs $a \cup b \cup X$, $a \cup c \cup X$, $a \cup d \cup X$, $c \cup d \cup X$. These four induced subgraphs have $n$ vertices and have the same number of edges. Therefore $$A+B+S=A+C+S=A+D+S=C+D+S+1,$$ and this is a contradicting equation.