2
$\begingroup$

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.

  • 0
    Are you sure 'distinct' is the right adjective? To me 'disjoint' would seem much more appropriate.2012-12-27
  • 0
    @TaraB It was meant to be paths.In regards to the adjective being distinct/disjoint,I would assume they are interchangeable2012-12-27
  • 0
    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.2012-12-27
  • 0
    It's generally a very bad idea to start off by assuming the thing you want to prove!2012-12-27

2 Answers 2

0

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$).

  • 0
    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.2012-12-27
  • 0
    @Chris ......I understand what you mean but should i write it in english2012-12-27
  • 0
    @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.2012-12-27
  • 0
    @Chris: Well, that's what I would have thought, but maybe not, considering the current 'proof' in the question.2012-12-27
0

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?

  • 0
    I have discounted the last point but i am not sure how to go about it.2012-12-27
  • 0
    i have improved my proof.Would you consider my proof correct/strong2012-12-27
  • 0
    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 =] ).2012-12-27
  • 0
    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$".2012-12-27
  • 0
    @ I was trying to follow the sample guide you gave me2012-12-27
  • 0
    let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/6860/discussion-between-jack-welch-and-tara-b)2012-12-27
  • 0
    @Jack: I wasn't there when you asked to start the chat. I wrote some things there later on. Let me know whether you can see them. I'm not quite sure how chat works.2012-12-27