# a 2-regular graph is cyclic or not?

We know the common result : - If every vertex of a graph G has degree at least2, then G contains a cycle. Can I conclude that 2-regular graphs are cycles where degree is exactly two of every vertex? I am not getting any contradictory example. Please help me if am wrong. Need some help.

I worked like this: If the graph G has n vertices of degree two. Let us assume that all vertices have degree two except two vertices, say vertex v and u. now to make degree two of vertex v and u, we must attach them with other vertices. only possible case is to make vertices u and v together. otherwise if we make them adjacent to some other vertex, then degree of that vertex will be three or more. Contradiction. Is my conclusion right?

NOTE: $G$ is a connected graph.

## 4 Answers

Suppose $G$ isn't cyclic. We know that $G$ contains at least one cycle $C$ (because every graph with $\delta (G)>1$ contains a cycle). $G$ is connected and that means that there exists vertices, for example $v$, that are not in $C$ but are neigbors to some vertices in $C$, for example $w \in C$. But since $w$ is in cycle, it has some neigbors that are too in that cycle, for example $w_1, w_2$. So if $w$ is adjacent at the same time to $w_1, w_2$ and $v$ then $deg(w)>2$ and that is contradiction because $G$ is $2$-regular thus there are no vertices with degree greater than $2$.

I am not getting any contradictory example.

Here's one: consider the graph $G(\mathbb{Z}, E)$ where $E$ is the symmetric closure of $\{(x, x+1) \mid x \in \mathbb{Z}\}$.

An infinite 2-regular graph can contain chains. A finite 2-regular graph is a collection of cycle graphs, and so a finite connected 2-regular graph is a cycle graph.

• I do not understand how is your example a 2-regular graph. Consider for example vertex '1'. It is adjacent to '2' which is adjacent to '3' so the edge set is symmetric closure of {......(1,2),(2,3),......}. which contains edges (1,2),(2,1),(2,3),(3,2) thus vertex '2' has degree 4 instead of 2. This argument holds for any vertex. Please explain how does this represent a 2-regular graph. Maybe provide some other example where an infinite 2-regular graph is not a cycle or not the disjoint union of cycles. – Madhur Panwar Jan 15 '18 at 8:27
• @MadhurPanwar, if you want a regular directed graph where every vertex has in-degree 1 and out-degree 1 just remove "symmetric closure". My example works either as a 2-regular undirected graph or as a regular directed graph where each vertex has in-degree 2 and out-degree 2. – Peter Taylor Jan 15 '18 at 8:46

Note that if $G$ is connected then in the case that every vertex has a degree of exactly 2, not only that there exists a cycle, there exists an Eulerian cycle (in which you use every edge exactly once).

• that is quite evident from the result that if a graph contains vertices of even degree, then its an eulerian graph – monalisa Sep 2 '14 at 12:39
• I mean to ask that can we directly say that this $G$ is only cycle graph, no other graph? – monalisa Sep 2 '14 at 12:42
• Still not so clear.. Do you mean to ask if there is only one 2-regular connected graph? – Snufsan Sep 2 '14 at 12:44
• yes. I mean the same. Is there only one 2-regular graph and that is cycle – monalisa Sep 2 '14 at 12:50

Let $u$ and $v$ be two adjacent nodes: we can say that $u$ is predecessor of $v$ (in a complete arbitrary way) and, given that $w$ is the (only) other neighbour of $v$, $v$ is the predecessor of $w$. Continue extending the chain in both directions: intermediate nodes have no other neighbours except the adjacent nodes in the chain. The chain $\Gamma$ closes in a cycle when its endpoints are adjacent in the graph. Assume that some vertex $a$ of the original graph does not belong to $\Gamma$: then there is no path from $u$ to $a$, so $G$ has more than a connected component, contradiction. This gives that $G$ must be isomorphic to a cycle graph.

If you remove the connection assumption, you have that any $2$-regular graph is isomorphic to a disjoint union of cycle graphs.