# Discrete Math Proof question for graphs with degree at least 2

Prove that a graph with minimum vertex degree at least two must contain a cycle.

To prove: $$\exists G = (V,E)$$ such that $$\forall v\in V(G), deg(v) \geq 2$$ $$\wedge \exists C_{k} \subseteq G$$ such that $$k \geq 3$$.

Let us assume a graph $$G=(V,E)$$ such that $$\forall v\in V(G), deg(v) \geq 2$$, since $$G$$ has connected components, $$\exists P_{k}\subseteq G$$ such that $$P_{k}$$ is the longest path in G and $$k \geq 2$$. If $$P_{k}$$ is a path graph, it must have two end vertices $$u,v \in P_{k}$$ such that $$deg(u) = deg(v) = 1$$, however the assumption states on the contrary that $$deg(u) \geq 2 \wedge deg(v) \geq 2$$. Therefore, we need to increase the degrees of u and v by 1 at least. There are two ways this can be done.

Case 1: Add an edge $${u,v} \in E(G)$$, then {u,v} edge is incident to both u and v, increaseing their degree by one, and we also get a cycle

Case 2: Add 2 edges {u,z} $$\in E(G) \wedge$$ {v,p} $$\in E(G)$$ such that $$z \neq u \neq v$$ and $$p \neq u \neq v$$ and $$p,z \in V(G)$$. Then we get two cycles in G

Since both of the cases covered creates cycle as subgraph, it must be the case that claim holds.

Is this proof accurate or there are cases I miss, if so, I would appreaciate it if you can explain. Thank you. If this is possible to prove via induction, please do that as well.

• The question statement seems to ask you to show the existence of a graph, not prove something. In that case, can't you take $C_3$? Apr 25, 2021 at 11:34
• Hey, my bad, I tried to show it via math language but I think I messed it up, here is the proof: Prove that a graph with minimum vertex degree at least two must contain a cycle. Apr 25, 2021 at 11:36