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.

Let u and v be distinct vertices of a graph.Prove that if there exists at least two distinct paths in the graph from u to v ,then the graph contains a simple circuit.

.I have started by defining a few things A simple circuit is a circuit in which except for the first and last vertices which are the same,there are no repeated vertices.

The two paths which start from u and end at v are said to be distinct if they do not have the same internal vertex in common or the same internal edge in common.

With the new information received,I would start by assuming that this graph contains a simple circuit with vertices a,b,c,d,e,f it has edges ab,bc,cd,de,ea which make up the simple circuit . where a=U and d=V. If there existed only one distinct path,there would be no way back from d to a which would give a simple circuit therefore a graph would have to have at least two distinct paths to have a simple circuit.

I would like my proof to be scrutinized.

share|improve this question
    
Are you sure 'distinct' is the right adjective? To me 'disjoint' would seem much more appropriate. –  Tara B Dec 27 '12 at 0:06
    
@TaraB It was meant to be paths.In regards to the adjective being distinct/disjoint,I would assume they are interchangeable –  Jack welch Dec 27 '12 at 0:23
    
Well, I would call a pair of paths distinct unless they are exactly the same path, but it's possible that 'distinct' is defined to have a different meaning from the usual one in this context. –  Tara B Dec 27 '12 at 0:27
    
It's generally a very bad idea to start off by assuming the thing you want to prove! –  Tara B Dec 27 '12 at 1:40

2 Answers 2

up vote 0 down vote accepted

First, you should convince yourself that your graph has a circuit: follow one path from $u$ to $v$, and the other to go from $v$ back to $u$. If these paths are distinct in the sense you have defined, no internal vertex or edge in common, then the paath just constructed should be a simple circuit (why?). Even if your paths are not distinct, say they share some but not all vertices in common, or, some but not all edges in common, you should be able to locate a simple circuit by noting the first vertex or edge the two paths have in common (other than $u$ or $v$).

share|improve this answer
    
Oh, I was aiming at giving the OP a chance to answer the question without further guidance by just pointing out that the thing about isolated or pendant vertices isn't needed. Oh well. –  Tara B Dec 27 '12 at 0:24
    
@Chris ......I understand what you mean but should i write it in english –  Jack welch Dec 27 '12 at 0:27
    
@Tara - I don't really like to give complete solutions unless they are asked for, so I guess I violated my own guidelines. I posted the answer and said to myself well I've gone and solved it for the OP, haven't I? At least close enough to a solution. –  Chris Leary Dec 27 '12 at 5:33
    
@Chris: Well, that's what I would have thought, but maybe not, considering the current 'proof' in the question. –  Tara B Dec 27 '12 at 6:40

I think you may be getting distracted by the last point you mentioned. You don't need it. You can construct your simple circuit from the two distinct paths from $u$ to $v$.

Let $p$ and $q$ be distinct paths from $u$ to $v$, and let $\overline{q}$ be the reverse of $p$ (so $\overline{q}$ goes from $v$ to $u$). Then $p\overline{q}$ is a circuit. Is it a simple circuit?

share|improve this answer
    
I have discounted the last point but i am not sure how to go about it. –  Jack welch Dec 27 '12 at 0:30
    
i have improved my proof.Would you consider my proof correct/strong –  Jack welch Dec 27 '12 at 0:40
    
Sorry, I have to go and do a few things now, but I will check it in about half an hour. By the way, since you're new here I'll just mention that it's considered good etiquette to upvote answers you find helpful. My impression is that you found both mine and Chris's answers helpful (it doesn't matter so much about mine, since I get the tick anyway =] ). –  Tara B Dec 27 '12 at 0:42
    
No, I wouldn't consider your proof to be correct. It is pretty much a proof of the converse of the statement you want to prove, i.e. "If a graph $\Gamma$ contains a simple circuit, then there exist vertices $u$ and $v$ in $\Gamma$ such that there are two distinct paths in $\Gamma$ from $u$ to $v$". –  Tara B Dec 27 '12 at 1:38
    
@ I was trying to follow the sample guide you gave me –  Jack welch Dec 27 '12 at 1:55

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.