Cycle does not Contain Subcycles

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $G$ be a cycle graph.

Then the only cycle graph that is a subgraph of $G$ is $G$ itself.


Proof

Aiming for a contradiction, suppose that $G$ contains a subgraph $C$ such that:

$C$ is a cycle graph
$C \ne G$ is non-empty.

Then there exists some vertex $v$ that is not in $C$.

Let $u$ be any vertex of $C$.

Since $G$ is a cycle graph, it is connected.

Therefore there is a walk from $u$ to $v$ in $G$.

There must be some vertex $x$ that is the last vertex in $C$ along that walk.

Therefore, $x$ is adjacent to a vertex not in $C$.

Thus it has a degree of at least $3$.

But $G$ is a cycle graph and every vertex in a cycle graph has degree $2$.

The result follows by Proof by Contradiction.

$\blacksquare$