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
    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
    @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
    @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