1
$\begingroup$

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.

$\endgroup$
2
  • $\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

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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