Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Prove that every undirected finite graph with vertex degree of at least 2 has a cycle.

Intuition-wise i need to prove that there's at least one 'tight -connection'. In other words, Proving that 2 vertexes {$v_i,v_{i+1}$}∈E exists so there's a way to reach from $v_i$ to $v_{i+1}$ and the other way around.

But since i am pretty new to graph theory, I'm not sure i'm even thinking about the question right. Any help would be nice.

share|improve this question
1  
A finite graph, presumably? –  copper.hat May 10 '13 at 17:29
    
Right, Edited the question. –  StationaryTraveller May 10 '13 at 17:39

8 Answers 8

up vote 8 down vote accepted

Start anywhere, and follow the edges. You'll always be able to continue, since each vertex has degree at least 2, so there will be an unused edge to exit on. If you ever return to a vertex where you've been, you've got a cycle. Otherwise, if the graph is finite, eventually you'll run out of unused vertices and you'll have to revisit some vertex.

share|improve this answer
    
So it's a kind of recursional thinking: For the first vertex i'll choose two other vertex $v_1$ and $v_2$. Each of those needs to 'choose' at least one more vertex. if it picks $v_2$ we are done, If not we call it again - And stop if we either revisited a vertex or the above is right? –  StationaryTraveller May 10 '13 at 17:37
3  
Think about building a path. Start with arbitrary $v_1$. Take any edge heading out, now you have $v_1-v_2$. Take any edge out from $v_2$, now you have $v_1-v_2-v_3$. Eventually you'll get an edge from the last vertex to one of the earlier ones in the path. –  vadim123 May 10 '13 at 17:41
    
I think i got it, Thanks. –  StationaryTraveller May 10 '13 at 17:43

Of all simple paths in $G$, find one with the most number of vertices, call it $P$. Let $v$ be one of the endpoints of the path, which must have at least one other neighbour. Since $P$ is maximal this neighbour already belongs to $P$, forming a cycle.

[This is somewhat constructive in that it gives partial information about where a cycle lies. Essentially it is the standard proof that every (non-tiny) tree has at least two leaves, alluded to in Brian's answer.]

share|improve this answer

If you’ve already learned about trees, you know that if $G$ is connected and does not have a cycle, then it’s a tree. Even if it’s not connected, its connected components must be trees (i.e., $G$ itself is a forest). And every tree has at least one leaf ...

share|improve this answer

By contradiction. Assume there is no cycle. Thus, starting at any vertex and going to neighbors through another edge (as there are two edges at least, you can do this each time) you never reach a vertex already visited. But that would mean that the vertex set is infinite.

share|improve this answer
    
Thanks, And I pretty much think that is the shortest way of proving it, But i'm looking out on how to understand it without using contradiction methods. –  StationaryTraveller May 10 '13 at 17:40

How I would approach this: Assuming that in an ungraph there can be only 1 edge which connects 2 vertices, if the graph has vertex degree of at least 2 then the smallest satisfiable graph must contain 3 vertices {V1, V2, V3} connected as a triangle where the set of edges would be {E12, E13, E23}. If you proceed to add a vertex V4, then in order to satisfy the graph requirement 2 edges must be added from the set {E14, E24, E34} and thus another triangular cycle could be created. Designating these edges as Ex4, Ey4 where x,y are exclusively an element of {1, 2, 3}, Vx and Vy would be increased to degree 3 allowing the edge Exy to be removed and the graph would still be satisfiable.

share|improve this answer

Suppose $p=|V| < \infty$. Choose $v_1,v_2 \in V$ with $v_2$ is connected to $v_1$ and $v_2 \neq v_1$. Suppose we have chosen $v_n$, then since the vertex degree is at least 2, we can always choose $v_{n+1} \notin \{v_n, v_{n-1}\}$. Continue until we have the sequence $v_1,...,v_{p+1}$. By the pigeon hole principle, some vertex must be repeated, ie, we must have $i,j$, with $i<j$ such that $v_i = v_j$. By construction, we must have, in fact, $i+1<j$, hence $(v_i,...,v_j)$ is a cycle.

share|improve this answer

Another option is using :$2|E|=\sum_{v\epsilon V}deg(v)$.

Let $G(V,E), |V|=n$

Since $deg(v)\ge2$ then: $2|E|=\sum_{v\epsilon V}deg(v)\ge\sum_{v\epsilon V}2\ge2n$

So we get $2|E|\ge2n \to |E|\ge n$

And using the statement: Every undirected graph with $n\ge 3$ vertices and $m\ge n$ vertices has a cycle.

share|improve this answer
1  
To add, a tree has at most $n-1$ edges. And a tree is the maximal case of an acyclic graph. Otherwise, we have a forest, which is a union of disjoint trees. –  ml0105 Apr 3 at 17:32

If every vertex of a graph G has degree at least 2, then G contains a cycle. pf. ² If G contains any loops or multiple edges, the result is trivial. (Assume simple) ² Construct a walk v0 to v1 to... by inductively picking vi+1 to be any vertex adjacent to vi . (Hypothesis guarantees existence) ² Since G has only finitely many vertices, we must eventually get a first repeat, vk. ² Part of walk between occurring between vk is a cycle.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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