I know I'm probably wrong, maybe someone can explain it to me. I'm doing practice problems in preparation for a test that is coming up.
- Let u and v be two vertices in a graph G. Show that if G has two simple paths between vertices u and v, then G has a simple circuit.
Sol: Assume that G has the following two simple paths: (u,..P1..,v) and (v,..P2..,u). Therefore, G has the circuit (u,..P1..,v,..P2..,u). If this circuit has no repeated edges, then the proof is complete.
Otherwise, let (x,y) be the first edge that occurs in P1 and is repeated in P2. In this case, the circuit can be represented as follows: (u,..P1..,x,y,..P1..,v,..P2..,y,x,..P2..,u) This circuit can be reduced to become as follows: (u,..P1..,x,..P2..,u) where no edge in P1 is repeated in P2(because edge (x,y) was the first edge in P1 that is repeated in P2). Thus, the reduced circuit is simple.
I've marked the part I'm having trouble with in bold. I don't
understand how we can just strip out the y vertex and simplify the
graph. I suspect I'm not preparing the graph properly, but I've
uploaded an example image to show why the graph can't be simplified.
If you delete the edge that goes from $x$ to $y$, you get a simple circuit going from $u$ to $x$ and then back from $x$ to $u$ along a different path, and that's a simple circuit. It never goes to $y$, nor to $v$. The problem is only to show that there is at least one simple circuit. It's not required to include any particular vertices, such as $y$ and $v$.