1
$\begingroup$

Let $G = (V, E)$ be a simple undirected graph of $n$ vertices. Suppose that $G$ is connected and that every vertex in $G$ has degree $2$. Show that $G$ must be a cycle graph.

Trial:

A graph $G = (V,E)$ is a cycle graph if

  1. $|V|\geq 3$
  2. the set of edges can be written as: $E=\{\{x_1,x_2\}, \{x_2,x_3\}, ……..\{x_n, x_1\}\}$

I can't bring the set of edges in the above form, i.e., I am not able to deduce it in the mathematical form.

$\endgroup$

2 Answers 2

2
$\begingroup$

You can use induction on $n$. For $n=3$ it is obviously.

Say we have now $n+1$ vertices. Say vertex $n+1$ is connected with $1$ and $n$. For a momement delete it and connect $1$ and $n$ (clearly $1$ and $n$ where not connected before since the graph is connected). Now we have new $G'$ connected graph with $n$ vertices and every vertex has again degree 2. So by induction hypothetis $G'$ is cycle. Destroy this cycle by deleting edge $1n$ and bring back vertex $n+1$ and you are done.

$\endgroup$
0
$\begingroup$

Everything's simplier. By Euler's Theorem: graph has an Euler cycle if and only if every vertex has even degree, vice versa we get that if every vertex of the graph has even degree, this graph is Eulerian, hence it's cyclic aswell. All the verticies of the given graph have even degree 2, therefore this graph is Eulerian, hence cyclic.

$\endgroup$

You must log in to answer this question.

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