Is it true that all paths between two vertices share a common point?

Question

I'm stuck on following graph theory problem:

suppose for two vertices $u$ and $v$ in an undirected graph $G$, any pair of paths between $u$ and $v$ share a common vertex (different from $u$ and $v$), then there exists vertex $w$ ($w\neq u,v$), which lies on all paths between $u$ and $v$.

I don't know if this statement is true, but can't come up with any counterexamples. how can I approach this problem?

Answer 1

This is a special case of Menger's theorem.

If any two $u,v$-paths share a common vertex, then the maximum number of vertex-disjoint $u,v$-paths we can find is at $1$; therefore by Menger's theorem, there is a $u,v$-cut of size $1$, which is the vertex $w$.

This is assuming we're not in one of several trivial cases:

• If there are no $u,v$-paths, then it's vacuously true that any two share a vertex. Let $w$ be any vertex other than $u$ and $v$, and the conclusion still holds.
• But if there are no vertices other than $u$ and $v$, we're in trouble.
• If $u$ and $v$ are adjacent, and there are no other $u,v$-paths, it's still vacuously true that any two $u,v$-paths share a vertex. But there is no vertex $w$ other than $u$ and $v$ which lies on the path consisting only of the edge $uv$, so in this case the conclusion does not hold.

Answer 2

If the property is not true there would be three paths $\alpha$, $\beta$ and $\gamma$ each meeting the other two in at least a vertex but not having a common vertex, except the end points.

Let $G^\prime$ be the subgraph consisting only of the vertices and edges that make up the paths $\alpha$, $\beta$ and $\gamma$.

This graph $G^\prime$ is planar because it contains no $K_{3,3}$ and no $S_5$. So embed it in $\Bbb R^2$.

The external region $F$ has the property that $\Bbb R^2\setminus\overline F$ is a connected open set in $\Bbb R^2$. Indeed the only way that it couldn't be connected is that there existed a point $w\in\Bbb R^2\setminus F$ disconnecting it, but this point would be common to the three paths and different from the end points.

Thus the boundary of $w\in\Bbb R^2\setminus F$ is a cycle including $u$ and $v$ and never passing through the same vertices twice. But any such cycle defines two paths (the "upper" path and the "lower" path, if we lay $G^\prime$ horizontally in the plane) that meet only at endpoints.