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.
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.
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.
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.
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.
Yet another proof. You will always going to have a vertex with degree odd or even. Erase an edge whenever a vertex has degree odd, taking care of no erasing an edge incident to a vertex of degree 2. The remaining graph has a closed Euler walk, thus having at least one cycle.
I think an another way to answer this is by induction. For case of n= 1 or 2 it is trivial. So the Induction Hypothesis is, assuming that every edge has at most degree 1: The statement holds true for $|| V || = n -1$.
Then the induction step is:
Suppose that we have a graph now of size $||V||=n$ and we remove 1 vertex and its incidental edge (which is at most 1). Then:
$$ ||V|| - 1 = n - 1 \geq ||E||-1 = (n-1)-1 = n-2 $$ Hence, $n-1 \geq n-2$. Which should hold for all graphs assuming that every vertex has at most degree 1
