0
$\begingroup$

I thought of proving it first for the cases where G is connected (so I would prove that G is a cycle), and later consider the cases where G is not connected and apply this result to each of the connected components of G, obtaining that G is a disjoint union of cycles.

If $\delta=2$, I could prove this by picking a vertex $v_1\in V(G)$ and, since $\delta=2$, pick $v_2\in V(G)$ such that it is one of the neighbors of $v_1$. Then we pick $v_3$ such that is a neighbor of $v_2$ and $v_3\neq v_1$. We iterate this process until we pick a vertex $v_n$ neighbor of $v_{n-1}$ such that $v_n\neq v_i$, $i=1,...,n-1$, so we have a path $L=v_1v_2.....v_{n-1}v_n$ of lenght $n-1$. Because $\delta=2$, $v_n$ must have another neighbor and the only option left is $v_1$. Thus, we get that G is a cycle.

However, since $\delta\ge2$, along this process I could be choosing a vertex $v_i$ that not only is neighbor of $v_{i-1}$ and $v_{i+1}$, but also of a vertex $v_j$, where $j=1,...,i-2$.

$\endgroup$

1 Answer 1

1
$\begingroup$

The total of the valencies of the vertices in a graph with $e$ edges is $2e$, and if the graph has $n$ vertices the mean valency is $2e/n$. Here the $e=n$ and so the mean valency is $2$, but also all vertices have valency $\ge2$ so every vertex has valency exactly two.

So at each vertex one can start a walk, leaving on one edge, and at each vertex leaving from the different edge to the one one arrived on, until one eventually reaches the start vertex, completing a cycle.

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