0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Madhur Panwar Jan 15 '18 at 8:27
  • $\begingroup$ @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. $\endgroup$ – Peter Taylor Jan 15 '18 at 8:46
1
$\begingroup$

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

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.