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.

  • $\begingroup$ 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$? $\endgroup$ Apr 25, 2021 at 11:34
  • $\begingroup$ 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. $\endgroup$ Apr 25, 2021 at 11:36

1 Answer 1


Given the clarification in comments, the proof is very simple via the contrapositive. If there is no cycle, the graph is a forest, but a forest always has leaves and those leaves have degree one, so the minimum degree is one.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .