MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let G be a simple connected graph. Let a, b, c, d be four distinct vertices of G.

Is there a way to partition the above four vertices to two pairs, so that the two shortest paths between the vertices of each pair are edge-disjoint?

share|cite|improve this question
Yes, it does seem to be possible in all cases. You might want to add some context to this question; right now, I'm not sure why this is an interesting problem. – Darsh Ranjan Oct 31 '09 at 21:56

Yes. Just pick the two paths (not necessarily edge disjoint) in G of shortest total length which together join the four vertices into two pairs. If they contained a common edge, you could remove that edge from both paths (changing which vertices are connected to which) to obtain a pair of paths of shorter total length. The resulting paths must be shortest paths between the pairs of vertices they connect. (I assume I'm allowed to pick any shortest path between two vertices, if there's more than one.) Any pair of shortest paths between the same pairs of vertices has the same total length, so by the same argument the two paths of the pair must be edge-disjoint.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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