Let G be a graph in which every vertex has degree 2. Is G necessarily a cycle?

Printable View

- Dec 15th 2009, 01:03 PMdynas7yGraph theory regarding cycles
Let G be a graph in which every vertex has degree 2. Is G necessarily a cycle?

- Dec 15th 2009, 01:11 PMPlato
- Dec 15th 2009, 03:31 PMdynas7y
What do you mean by is the number of edges the number of edges? Using the theorem to find the number of edges the number of edges would be 2n/2, where n is the number of vertices. So if n is odd then there are an odd number of edges and if n is even there are an even number of edges...

- Dec 15th 2009, 03:59 PMPlato
If a simple graph has n vertices, $\displaystyle |E|$ is the number of edges, and $\displaystyle \text{deg}(v_k)$ is the degree of vertex $\displaystyle v_k$

then $\displaystyle 2\left| E \right| = \sum\limits_k {\deg (v_k )} $.

That is a most basic idea in graph theory. - Dec 15th 2009, 04:22 PMdynas7y
I understand the theorem, which is what I explained in my post regarding the sum of the degrees and the number of edges. By the theorem, since each vertex has degree 2, then the number of vertices multiplied by 2 gives the sum of the degrees. Divide this by two gives you the number of edges. I'm not sure how this relates to the original question though of whether a graph with all of it's vertices having degree 2 is necessarily a cycle

- Dec 15th 2009, 04:42 PMPlato