Return to Revisions

We may find a regular subgraph with similar property, but I am not sure how does it lead to a full answer. Assume that $1,\dots,m$, $m>1$, are all vertices of the same degree $d$ (we may always assume so, since any graph with at least 2 vertices has two vertices with the same degree.) Let $A$ be adjacency matrix, then consider eigenspace of $A^2$ corresponding to eigenvalue $d-k$. It is easy to see that this is a space of dimension $m-1$, it consists of vectors $(x_1,\dots,x_n)$ for which $x_{m+1}=\dots=x_n=0$ and $x_1+\dots+x_{m}=0$. But eigenspace of $A^2$ is invariant for $A$. Thus any vector with these properties is invariant for $A$. It follows that any vertex $i>m$ is either joined with all $1,\dots,m$, or with none of them. So, $1,\dots,m$ form a regular subgraph with the same property but smaller $k$.