Return to Answer

I claim that for $k>1$ any such graph is regular, in this case we get a well-known problem (subproblem of describing strongly regular graphs), which does not seem to be solved completely. Case $k=1$ is itself known, friendly vertex exists in this case by the friendship theorem of Paul Erdős, Alfréd Rényi, and Vera T. Sós (1966), see Brendan's comment.

At first, if there exists a vertex of degree $k+1$, it is straightforward that $G$ is complete graph on $k+2$ vertices. If some vertex is joined with all other vertices, any other vertex has degree $k+1$, so we again get complete graph on $k+2$ vertices. Proceed with other cases.

At first, I consider a special case: $V=V_1\sqcup V_2$ for non-empty sets $V_1,V_2$, and all edges between $V_1$ and $V_2$ exist. Denote $n_1=|V_1|$, $n_2=|V_2|$, we have $n_1>1$, $n_2>1$, since there is no vertex joined with all other vertices. Choose vertices $v_i\in V_i$, $i=1,2$. Denote by $d_i$ their degrees in subgraphs $G(V_i)$. We have $d_1+d_2=k$, in particular, this does not depend on how we choose vertices. Next, any two vertices in $V_1$ have $k-n_2=d_1+d_2-n_2:=\alpha_1$ common neighbors in $V_1$. Let $W$ be a set of neighbors of $v_1$ in $G(V_1)$. Then counting edges between $W$ and $v_1\setminus (W\cup v_1)$ leads to a standard relation $(n_1-d_1-1)\alpha_1=d_1(d_1-\alpha_1-1)=d_1(n_2-d_2-1)>\alpha_1(n_2-d_2-1)$, i.e. $n_1-d_1-1>n_2-d_2-1$, analogously $n_2-d_2-1>n_1-d_1-1$. Contradiction.

Now assume that our graph is not regular and $1,\dots,m$, $n>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. Assume that there are $s$ vertices joined with all $1,\dots,m$. Then $s\leqslant k$. since they are common neighbors of $1,2$. By already considereв case there is another vertex $v$, not joined with $1,\dots,m$. But 1 and $v$ have at most $s$ common neighbors. Thus $s=k$. But vertex 1 has degree at least $k+2$, so it is joined with some vertices $u_1,u_2\in\{1,\dots,m\}$. These two vertices have at least $k+1$ common neighbors. Contradiction.

I claim that for $k>1$ any such graph is regular, in this case we get a well-known problem (subproblem of describing strongly regular graphs), which does not seem to be solved completely. Case $k=1$ is itself known, friendly vertex exists in this case by the friendship theorem of Paul Erdős, Alfréd Rényi, and Vera T. Sós (1966), see Brendan's comment. Ah, he have already found the general result aswell.

At first, if there exists a vertex $v$ of degree $k+1$, then $G$ is complete graph on $k+2$ vertices. (Indeed, considering $v$ and any its neghbor we see that $v$ and its neighbors form $K_{k+2}$. If there is another vertex $u$, considering $v$ and $u$ we see that $u$ must be joined with $k$ neighbors of $v$, but if so any two of them --- here we use that $k>1$ --- have more than $k$ common neighbors.) If some vertex is joined with all other vertices, any other vertex has degree $k+1$, so we again get complete graph on $k+2$ vertices. Proceed with other cases.

At first, I consider a special case: $V=V_1\sqcup V_2$ for non-empty sets $V_1,V_2$, and all edges between $V_1$ and $V_2$ exist. Denote $n_1=|V_1|$, $n_2=|V_2|$, we have $n_1>1$, $n_2>1$, since there is no vertex joined with all other vertices. Choose vertices $v_i\in V_i$, $i=1,2$. Denote by $d_i$ their degrees in subgraphs $G(V_i)$. We have $d_1+d_2=k$, in particular, this does not depend on how we choose vertices. Next, any two vertices in $V_1$ have $k-n_2=d_1+d_2-n_2:=\alpha_1$ common neighbors in $V_1$. Let $W$ be a set of neighbors of $v_1$ in $G(V_1)$. Then counting edges between $W$ and $v_1\setminus (W\cup v_1)$ leads to a standard relation $(n_1-d_1-1)\alpha_1=d_1(d_1-\alpha_1-1)=d_1(n_2-d_2-1)>\alpha_1(n_2-d_2-1)$, i.e. $n_1-d_1-1>n_2-d_2-1$, analogously $n_2-d_2-1>n_1-d_1-1$. Contradiction.

Now assume that our graph is not regular and $1,\dots,m$, $n>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. Assume that there are $s$ vertices joined with all $1,\dots,m$. Then $s\leqslant k$. since they are common neighbors of $1,2$. By already considered case there is another vertex $v$, not joined with $1,\dots,m$. But 1 and $v$ have at most $s$ common neighbors. Thus $s=k$. But vertex 1 has degree at least $k+2$, so it is joined with some vertices $u_1,u_2\in\{1,\dots,m\}$. These two vertices have at least $k+1$ common neighbors. Contradiction.

I claim that any such graph is regular, in this case we get a well-known problem (subproblem of describing strongly regular graphs), which does not seem to be solved completely.

At first, if there exists a vertex of degree $k+1$, it is straightforward that $G$ is complete graph on $k+2$ vertices. If some vertex is joined with all other vertices, any other vertex has degree $k+1$, so we again get complete graph on $k+2$ vertices. Proceed with other cases.

At first, I consider a special case: $V=V_1\sqcup V_2$ for non-empty sets $V_1,V_2$, and all edges between $V_1$ and $V_2$ exist. Denote $n_1=|V_1|$, $n_2=|V_2|$, we have $n_1>1$, $n_2>1$, since there is no vertex joined with all other vertices. Choose vertices $v_i\in V_i$, $i=1,2$. Denote by $d_i$ their degrees in subgraphs $G(V_i)$. We have $d_1+d_2=k$, in particular, this does not depend on how we choose vertices. Next, any two vertices in $V_1$ have $k-n_2=d_1+d_2-n_2:=\alpha_1$ common neighbors in $V_1$. Let $W$ be a set of neighbors of $v_1$ in $G(V_1)$. Then counting edges between $W$ and $v_1\setminus (W\cup v_1)$ leads to a standard relation $(n_1-d_1-1)\alpha_1=d_1(d_1-\alpha_1-1)=d_1(n_2-d_2-1)>\alpha_1(n_2-d_2-1)$, i.e. $n_1-d_1-1>n_2-d_2-1$, analogously $n_2-d_2-1>n_1-d_1-1$. Contradiction.

Now assume that our graph is not regular and $1,\dots,m$, $n>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. Assume that there are $s$ vertices joined with all $1,\dots,m$. Then $s\leqslant k$. since they are common neighbors of $1,2$. By already considereв case there is another vertex $v$, not joined with $1,\dots,m$. But 1 and $v$ have at most $s$ common neighbors. Thus $s=k$. But vertex 1 has degree at least $k+2$, so it is joined with some vertices $u_1,u_2\in\{1,\dots,m\}$. These two vertices have at least $k+1$ common neighbors. Contradiction.

I claim that for $k>1$ any such graph is regular, in this case we get a well-known problem (subproblem of describing strongly regular graphs), which does not seem to be solved completely. Case $k=1$ is itself known, friendly vertex exists in this case by the friendship theorem of Paul Erdős, Alfréd Rényi, and Vera T. Sós (1966), see Brendan's comment.

At first, if there exists a vertex of degree $k+1$, it is straightforward that $G$ is complete graph on $k+2$ vertices. If some vertex is joined with all other vertices, any other vertex has degree $k+1$, so we again get complete graph on $k+2$ vertices. Proceed with other cases.

At first, I consider a special case: $V=V_1\sqcup V_2$ for non-empty sets $V_1,V_2$, and all edges between $V_1$ and $V_2$ exist. Denote $n_1=|V_1|$, $n_2=|V_2|$, we have $n_1>1$, $n_2>1$, since there is no vertex joined with all other vertices. Choose vertices $v_i\in V_i$, $i=1,2$. Denote by $d_i$ their degrees in subgraphs $G(V_i)$. We have $d_1+d_2=k$, in particular, this does not depend on how we choose vertices. Next, any two vertices in $V_1$ have $k-n_2=d_1+d_2-n_2:=\alpha_1$ common neighbors in $V_1$. Let $W$ be a set of neighbors of $v_1$ in $G(V_1)$. Then counting edges between $W$ and $v_1\setminus (W\cup v_1)$ leads to a standard relation $(n_1-d_1-1)\alpha_1=d_1(d_1-\alpha_1-1)=d_1(n_2-d_2-1)>\alpha_1(n_2-d_2-1)$, i.e. $n_1-d_1-1>n_2-d_2-1$, analogously $n_2-d_2-1>n_1-d_1-1$. Contradiction.

Now assume that our graph is not regular and $1,\dots,m$, $n>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. Assume that there are $s$ vertices joined with all $1,\dots,m$. Then $s\leqslant k$. since they are common neighbors of $1,2$. By already considereв case there is another vertex $v$, not joined with $1,\dots,m$. But 1 and $v$ have at most $s$ common neighbors. Thus $s=k$. But vertex 1 has degree at least $k+2$, so it is joined with some vertices $u_1,u_2\in\{1,\dots,m\}$. These two vertices have at least $k+1$ common neighbors. Contradiction.

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

I claim that any such graph is regular, in this case we get a well-known problem (subproblem of describing strongly regular graphs), which does not seem to be solved completely.

At first, if there exists a vertex of degree $k+1$, it is straightforward that $G$ is complete graph on $k+2$ vertices. If some vertex is joined with all other vertices, any other vertex has degree $k+1$, so we again get complete graph on $k+2$ vertices. Proceed with other cases.

At first, I consider a special case: $V=V_1\sqcup V_2$ for non-empty sets $V_1,V_2$, and all edges between $V_1$ and $V_2$ exist. Denote $n_1=|V_1|$, $n_2=|V_2|$, we have $n_1>1$, $n_2>1$, since there is no vertex joined with all other vertices. Choose vertices $v_i\in V_i$, $i=1,2$. Denote by $d_i$ their degrees in subgraphs $G(V_i)$. We have $d_1+d_2=k$, in particular, this does not depend on how we choose vertices. Next, any two vertices in $V_1$ have $k-n_2=d_1+d_2-n_2:=\alpha_1$ common neighbors in $V_1$. Let $W$ be a set of neighbors of $v_1$ in $G(V_1)$. Then counting edges between $W$ and $v_1\setminus (W\cup v_1)$ leads to a standard relation $(n_1-d_1-1)\alpha_1=d_1(d_1-\alpha_1-1)=d_1(n_2-d_2-1)>\alpha_1(n_2-d_2-1)$, i.e. $n_1-d_1-1>n_2-d_2-1$, analogously $n_2-d_2-1>n_1-d_1-1$. Contradiction.

Now assume that our graph is not regular and $1,\dots,m$, $n>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. Assume that there are $s$ vertices joined with all $1,\dots,m$. Then $s\leqslant k$. since they are common neighbors of $1,2$. By already considereв case there is another vertex $v$, not joined with $1,\dots,m$. But 1 and $v$ have at most $s$ common neighbors. Thus $s=k$. But vertex 1 has degree at least $k+2$, so it is joined with some vertices $u_1,u_2\in\{1,\dots,m\}$. These two vertices have at least $k+1$ common neighbors. Contradiction.