|
I am trying to prove that if a finite graph has no isolated or pendant vertices then it contains at least one simple circuit. Let the graph with no isolated or pendant vertices be $(V,E)$. A path in the graph cannot exceed $|V|-1$ since a path of length $m$ passes through $m+1$ vertices. I do not know where to go from here. |
|||||||||||
|
|
HINT: By hypothesis $\deg(v)\ge 2$ for each $v\in V$. Let $v_0$ be any vertex. There is a vertex $v_1$ adjacent to $v_0$. Since $\deg(v_1)\ge 2$, there is a vertex $v_2$ adjacent to $v_1$ such that $v_2\ne v_0$. Keep going in this fashion: given $v_k$ with $k\ge 1$, let $v_{k+1}$ be a vertex adjacent to $v_k$ and different from $v_{k-1}$. $V$ is finite, so eventually you must have $v_k=v_\ell$ for some $k<\ell$. What can you say about $\{v_k,v_{k+1},\dots,v_\ell\}$? |
|||||
|
|
Different hint: Every vertex has degree at least two, so the sum of the degrees of the vertices is at least $2|V|$. Being careful about non-connected graphs, show that such a graph cannot be a forest (disjoint collection of trees). |
|||||||
|
