Does edge contraction increases the degree of a regular graph

Question

Definition: A contraction of an edge represents the merging of the coalitions associated to its incident vertices. Definition: A graph G is said to be regular, if all its vertices have the same degree.

It is trivial that contraction of any edge in a cycle $C_n$, $n \geq 4$ retains the degree of the graph.

Is there any regular graph different from $C_n$, $n \geq 4$ such that the graph obtained by contracting any edge is still regular?

Answer 1

The only examples are:

1. A complete graph $K_n$. It is $(n-1)$-regular; after contracting an edge, what is left is $K_{n-1}$, which is $(n-2)$-regular.

2. A union of disjoint cycles, slightly generalizing your example. May contain infinite paths as special cases of "cycle" if you allow infinite graphs.

3. A graph completely without edges. This may or may not count, depending on how we parse your the word "any" in your condition. If it encodes a "for all edges", the edgeless graph vacuously satisfies the condition.

To see that these are all the possibilities, suppose that an $n$-regular graph has at least 3 vertices and has at least one edge that we can contract to produce another regular graph. After contracting, every vertex that was not incident to the contracted edge has degree either $n$ or $n-1$.

If the contracted graph is $(n-1)$-regular. Then every other vertex must have been connected to both ends of the edge we contracted, and there must be exactly $n-1$ of them for the endpoints to have had degree $n$. So the graph had $n+1$ vertices and the only way for it to be $n$-regular was for it to be complete.

On the other hand, if the contracted graph is still $n$-regular it means that there was no vertex that was connected to both ends of the edge. Therefore the contracted vertex now has degree $2(n-1)$. But this needs to equal $n$, and $2(n-1)=n$ implies $n=2$, so the graph was a union of disjoint cycles.

This analysis does not consider graphs with fewer than 3 vertices, but they are either $K_2$ (and contracting its single edge produces a $0$-regular point) or are edgeless, so there are no new cases there.