Find $G$ if $G-v$ is regular $\forall v \in V$

Question

Find all graphs $G$ that satisfy the following:

$G-v;\;\;\forall v \in V(G)$ is regular.

Not sure if this is correct: If there are no edges in $G$ then the condition is satisfied and a graph of isolated vertices is an example.

So assume there is at least one edge.

If $G-v_1$ is $k$-regular, say. Then $d(v_1)=k+1$.

let $v_2\in N_G(v_1)$.

$G-v_2$ is regular as well, so $v_2$ in $G$ must be adjacent to all other vertices in $N_G(v_1)$.

Now assume there is a $v_3 \notin N_G(v_{1,2})$. But for $G-v_3$ to be regular, $v_1v_2, v_2v_3 \in E(G)$, so by contradiction, there is no such $v_3$. $G$ must then be complete since $v_1$, $v_2$ are arbitrary vertices.

But for $3$ vertices, there is the path of length 2 and the graph with $3$ vertices and $1$ edge, both which are not complete but satisfy the condition.

Answer 1

Let $C$ be a component of $G$.

If $|C| = 1$, then $G$ is either a graph of isolated vertices or the graph with $3$ vertices and $1$ edge. If $|C| = 2$, then $G$ is the graph with $3$ vertices and $1$ edge.

Suppose $|C| \ge 3$. Then $G$ must be connected:

Assume that $G$ has another component $C' \neq C$ and let $v \in C$ and $v' \in C'$. Then $G - v$ is a regular graph, say of valency $k$, and similarly $G - v'$ is regular of valency $k'$. So $C$ is $k'$-regular and $C'$ is $k$-regular. Now, because $C - v$ is $k$-regular (which is the same valency of $C'$), it follows that $k' > k$ (the neighbors of $v$ in $C$ lost one degre). Similarly, by the symmetry of the problem, we can also state that $k > k'$, which is a contradiction.

Now, suppose that $G$ is not the path on $3$ vertices. We'll prove that $G - v$ is $k$-regular for all $v \in G$ for a fixed integer $k$ and $G$ will be complete by your reasoning:

Let $v, v'$ be two distinct vertices in $G$ and let $k, k'$ denote the valencies of $G - v$ and $G - v'$, respectively. Since $G$ is connected and $|G| \ge 3$, $N(v)$ and $N(v')$ are both nonempty. We have $d(u) = k + 1$ for all $u \in N(v)$ and $d(u') = k' + 1$ for all $u' \in N(v')$. If $N(v) \cap N(v') \neq \emptyset$, we already have $k = k'$. Suppose by contradiction that $N(v) \cap N(v')$ is empty. Then, for some $u \in N(v)$, we have $$ k + 1 = d_G(u) = d_{G - v'}(u) = k', $$ unless $N(v) = \{v'\}$. Similarly, for some $u' \in N(v')$, we have $$ k' + 1 = d_G(u') = d_{G - v}(u') = k, $$ unless $N(v') = \{v\}$. If both equations were true we would get a contradiction, so we may assume that $N(v) = \{v'\}$. But then $G - v'$ has no edges and hence every edge of $G$ is incident with $v'$, which implies that $G$ is the path on $3$ vertices, a contradiction. Therefore $N(v) \cap N(v')$ is not empty and the result follows.