3
$\begingroup$

My course notes defined a cycle graph as follows: A cycle graph is a simple graph on $n \geq 3$ vertices in which all vertices have degree $2$.

However, I'm not sure why does this definition work. The more intuitive definition of a cycle graph I found on Wikipedia says that

A cycle graph [...] is a graph that consists of a single cycle.

Therefore, I'm trying to show how are these two definitions connected by proving that

For all connected simple graphs $G = (V,E)$, $|V| \geq 3 \land (\forall v \in V, $ the degree of $v = 2) \iff G$ is a graph that consists of a single cycle.

The '$\impliedby$' direction proof is straightforward, but I can't think of how to prove the implication in the opposite direction.

$\endgroup$

2 Answers 2

4
$\begingroup$

Let G be a connected simple graph where every vertex has degree 2. Let P be a path of maximal length in G, and let u and v be the origin and terminus of that path. Let u' be the neighbor of u that is not the "next" vertex in the path, and let v' be the neighbor of v that is not the "next-to-last" vertex in the path. Since P cannot be extended in either direction, it must be that u' and v' are already vertices in P. But the neighbors of each internal vertex of the path already have both of their neighbors used. So it must be that u'=v and v'=u. Hence, connecting the ends of the path lead to a cycle.

$\endgroup$
0
$\begingroup$

The argument below is not what one should write formally, but as is often the case in Mathematics, is more illustrative than a formal graph theoretic argument:

Start with any vertex $v_1$ of the graph. Let $v_2$ be one of the two neighbors of $v_1$. Let $v_3$ be the only neighbor of $v_2$ other than $v_1$. Now, one of the neighbors of $v_3$ is $v_2$, and if the other neighbor is $v_1$, then $v_1v_2v_3$ forms a $3$-cycle and the graph is completed, since every vertex has degree $2$ and the graph is connected. So, assume that $v_3$ is a neighbor of some $v_4 \notin \{v_1,v_2,v_3\}$. Clearly, $v_4$ cannot be connected to $v_2$, since then $v_2$ would have degree $3$. If $v_4$ has $v_1$ as a neighbor, then we have completed a $4$-cycle, and are done by the same logic above. So, suppose that $v_4$ is a neighbor of some $v_5 \notin \{v_1,v_2,v_3,v_4\}$. In this way, suppose that we get a path $v_1v_2\ldots v_m$ for some $m$. Clearly, $v_m$ cannot be connected to either of $v_2,v_3,\ldots, v_{m-2}$, since then that vertex would have degree $3$. If $v_m$ is connected to $v_1$, we complete an $m$-cycle. So, the only option left is, $v_m$ is connected to some new vertex $v_{m+1}$. But this cannot go for ever, since we have only $n$ vertices in store. So, the graph must be a cycle.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .