# Graph theory regarding cycles

• Dec 15th 2009, 02:03 PM
dynas7y
Graph theory regarding cycles
Let G be a graph in which every vertex has degree 2. Is G necessarily a cycle?
• Dec 15th 2009, 02:11 PM
Plato
Quote:

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

You know that twice the number of edges equals the degree sum.
Does this mean that the number of edges is the number of edges?
So what is the conclusion?
• Dec 15th 2009, 04:31 PM
dynas7y
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, 04:59 PM
Plato
Quote:

Originally Posted by dynas7y
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...

If a simple graph has n vertices, $|E|$ is the number of edges, and $\text{deg}(v_k)$ is the degree of vertex $v_k$
then $2\left| E \right| = \sum\limits_k {\deg (v_k )}$.

That is a most basic idea in graph theory.
• Dec 15th 2009, 05:22 PM
dynas7y
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, 05:42 PM
Plato
Quote:

Originally Posted by dynas7y
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

I must say that I do not think that understands the implication of this material.
Every vertex has two concurrent edges.
There are no other possibilities.