Cycles do not contain subcycles

From ProofWiki
Jump to: navigation, search

Theorem

If a graph $G$ is a cycle graph, then the only cycle graph that is a subgraph of $G$ is $G$ itself.


Proof

Suppose that $G$ contains a subgraph $C$ that is a cycle graph and $C \ne G$ is non-empty.

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

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

Since $G$ is a cycle, 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 and every vertex in a cycle has degree $2$: a contradiction.

$\blacksquare$

Personal tools
Namespaces
Variants
Actions
Navigation
ProofWiki.org
ToDo
Toolbox
Google AdSense