I am trying to solve the following exercise about 3-connected graphs from this book.

  1. (a) Show that for every two vertices $u$ and $v$ of a $3$-connected graph $G$, there exist two internally disjoint $u$-$v$ paths of different lengths in $G$.

    (b) Show that the result in (a) is not true in general if $G$ is $2$-connected.

Whitney's Theorem states that a graph $G$ is $k$-connected if and only if any two vertices of $G$ are connected by at least $k$ vertex disjoint paths, so for part (a) we have that every two vertices $u$ and $v$ are connected by at least $3$ internally disjoint paths. I suppose I should use this result and try to make a proof by contradiction, but it does not work. Any hints?


Consider 3 different paths $A, B, C$ between $u$ and $v$. If one of the paths is length $1$, the other two must be longer, and we are done. Also if the paths are different lengths then we are also done. Otherwise choose two points on two of the paths arbitrarily, say $p$ on $A$ and $q$ on $B$, and find three distinct paths between them. At least one of these paths does not go through either $u$ or $v$, so examine this one, $D$.

Now if $D$ crosses $C$, find the nearest point on $D$ that is also on $C$ to $p$ and call this $r$. Now either $uprv$ (along $ADC$) or $urpv$ (along $CDA$) is longer than $B$ as required.

Otherwise if $D$ does not cross $C$, then either $upqv$ (along $ADB$) or $uqpv$ (along $BDA$) is longer than $C$ as required.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.