Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

2 Answers 2

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\}$?

share|improve this answer
    
..Would it be write that because of the finite nature of the graph,l would surely be k.Which means its a circuit because the first and last vertice are the same with no repeated edges and vertices apart from the first and last vertices. –  Jack welch Jan 6 '13 at 18:29
    
@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).

share|improve this answer
    
..How did you arrive at every vertex having a degree of two.Shouldn't it be that every vertex should have a minimum degree of 2? –  Jack welch Jan 6 '13 at 18:27
    
Sorry, that is what I meant. :S –  Eric Stucky Jan 6 '13 at 18:27
    
@Thanks...I am just trying to understand your point –  Jack welch Jan 6 '13 at 18:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.