0
$\begingroup$

This question already has an answer here:

Prove that every graph in which each vertex has degree at least 2 must contain a cycle. Graph has a finite number of vertices

I need some clarification, I understand that a vertex with degree 2 means having 2 neighbors. So this means that every vertex has two neighbors does this mean that the shape is a triangle with 3 vertices and 3 edges all connected or a square where each vertex is connected to two other vertices. Since they are connect it forms a cycle. However Im having trouble proving it, how will I go about proving this? Thanks in advance

$\endgroup$

marked as duplicate by Ross Millikan, Macavity, JonMark Perry, draks ..., mlc May 31 '17 at 5:48

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ You asked the same question a day ago here It seems you missed the point that a cycle can include all the vertices of a graph, so you can't just look at triangles and squares. You should update the other question rather than asking a new one. $\endgroup$ – Ross Millikan May 31 '17 at 3:06
0
$\begingroup$

Suppose the opposite. We have a graph which the degree of each node is 2, but there is no cycle. So, we know that if it is connected will be a tree and $v = e + 1$. Therefore, we can conclude for this graph, $e$ must be less than or equal $v - 1$. On ther hand, we know in this graph each node has degree 2, so $e = 2\times v / 2 = v$. This is contradicted by $e \leq v - 1$. Therefore, the first assumption is not true, and this graph has at least one cycle.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.