# If a graph has no isolated or pendant vertices then it contains at least one simple circuit

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.

-
Maybe finite graphs. Counterexample: infinite binary tree. – alancalvitti Jan 6 '13 at 18:13
How much do you know about graphs? What about graphs that contain no circuits? – Eric Stucky Jan 6 '13 at 18:15
@alancalvitti: It’s clearly a question about finite graphs. – Brian M. Scott Jan 6 '13 at 18:17
A graph that contains no circuits is a tree.it is connected and has n-1 edges where n is the the number of vertices.It has at least one pendant vertice.Thats what i know – Jack welch Jan 6 '13 at 18:17
A graph with no circuits need not be a tree, because it need not be connected. It will be a forest, however: a forest is a graph whose connected components are trees. – Brian M. Scott Jan 6 '13 at 18:19

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\}$?
@Jack: You have the right idea, but you haven’t said it quite right: the indices $k$ and $\ell$ are not equal, but the vertices $v_k$ and $v_\ell$ are the same. It might have repeated vertices, but if you take care to specify that $\ell$ is the smallest index such that $v_k=v_\ell$ and $\ell>k$, then you’ll have a circuit. – Brian M. Scott Jan 6 '13 at 18:32
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).