Arguing that Graph, $G$, is 3 regular and pairwise edge-disjoint path can't share internal vertices

237 Views Asked by At

Let $G$ be a graph that is 3-regular. There are $n$ pairwise edge-disjoint $x,y$ paths. I want to show "since G is 3 regular, these paths cannot share internal vertices." I know the answer is supposed to be because it would force four distinct edges at a vertex. What I don't see is the argument that forces me to this conclusion.

1

There are 1 best solutions below

7
On BEST ANSWER

Hint: what happens if two of the n paths do indeed share internal vertices? What happens at that vertex?