Intereting Posts

A semigroup with identity having exactly one idempotent is a group
Given a $C_c^∞(G)$-valued random variable, is $C_c^∞(G)∋φ↦\text E$ an element of the dual space of $C_c^∞(G)$?
How to prove and interpret $\operatorname{rank}(AB) \leq \operatorname{min}(\operatorname{rank}(A), \operatorname{rank}(B))$?
Show $f$ is constant if $|f(x)-f(y)|\leq (x-y)^2$.
Calculating an Angle from $2$ points in space
Formula for $\zeta(3)$ -verification
“Empirical” entropy.
inversion of the Euler totient function
Is there a closed form equation for fibonacci(n) modulo m?
Implementation of Monotone Cubic Interpolation
What does it mean for a polynomial to be solvable by radicals?
Proofs of AM-GM inequality
Is this hierarchy of manifolds correct?
The density — or otherwise — of $\{\{2^N\,\alpha\}:N\in\mathbb{N}\}$ for ALL irrational $\alpha$.
Unexpected examples of natural logarithm

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.

- Powers of Adjacency Matrix (Determination of connection in Graph)
- Reorder adjacency matrices of regular graphs so they are the same
- Consequences of cycle space cut space duality
- Arrangement of integers in a row such that the sum of every two adjacent numbers is a perfect square.
- parity bias for trees?
- Maximum number of edges in a simple graph?

- Planar graphs with $n \geq 2$ vertices have at least two vertices whose degree is at most 5
- The time complexity of finding a neighborhood graph provided an unordered adjacency matrix
- Use Gröbner bases to count the $3$-edge colorings of planar cubic graphs…
- 3-regular graphs with no bridges
- Identity for sum of squares of vertex degrees in graph
- In graph theory, what is the difference between a “trail” and a “path”?
- prove or supply counter example about graph
- Trees whose complement is also a tree
- Returning Paths on Cubic Graphs Without Backtracking
- How does the topology of the graphs' Riemann surface relate to its knot representation?

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 …

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.

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.

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.

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.

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.

- Maximal ideal/ Prime ideal
- Showing that an integral domain is a PID if it satisfies two conditions
- Recovering eigenvectors from SVD
- Is it true that $\mathbb{C}(x) \equiv \mathbb{C}(x, y)$?
- $-4\zeta(2)-2\zeta(3)+4\zeta(2)\zeta(3)+2\zeta(5)=S$
- Proving Functions are Surjective
- Complex ($\mathbb C$) least squares derivation
- Existence of strictly positive probability measures
- Are there any countable Hausdorff connected spaces?
- Peano axioms with only sets and mapping
- Relation between rank and number of non-zero eigenvalues of a matrix
- Is it mathematically correct to write $a \bmod n \equiv b$?
- If $abc=1$ so $\sum\limits_{cyc}\frac{a}{\sqrt{a+b^2}}\geq\frac{3}{\sqrt2}$
- $\lim x \sin (1/x)$, when $x \to 0$
- How to prove that the set $A = \left\{ {p:{p^2} < 2,p \in {\Bbb Q^+}} \right\}$ has no greatest element?