Prove that every undirected finite graph with vertex degree of at least 2 has a cycle
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.
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.
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.]
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 ...
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.