Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given an undirected connected graph $G=(V,E)$ and two vertices $s,t \in V$ . We know that the length of the shortest path from s to t is bigger than $V / 2 $.

I would love your help with proving that there must be a vertex which if we would delete it, along with the edges going out of it, there won't be a path between $s$ and $t$.

sadly I didn't come with any smart conclusions.

Thanks!

share|improve this question

3 Answers 3

up vote 1 down vote accepted

It's actually not that hard. The proof goes like this:

1) Removing all the vertices on the shortest path will render s-t disconnected (obviously, since there is only $< V/2+1$ vertices left, which means any path is $< V/2$ edges, if it were a s-t path, it would contradict the shortest s-t path)

2) We construct an oriented graph, where

$V' = \{s, t\} \cup \{ v_+, v_- | v \neq s, t\}$

$E' = \{(x_-, y_+) | xy \in E\} \cup \{(x_+, x_-)| \{x_+, x_-\} \subset V' \} \cup \{(s, x_+)|sx \in E\} \cup \{(x_-, t) | xt \in E\}$

I assume st is not an edge in the original graph; if it were, it could only have less than 2 vertices, which contradicts there are vertices $s$ and $t$).

it can be easily shown any s-t path in the original graph corresponds to a s-t path in the new directed graph and vice versa.

3) max flow = min cut

We have a s-t flow in the new graph (flowing along the shortest path; capacities are all set to 1). It is maximal, because it disallows any other flow through its verticies (bc. $x_+\rightarrow x_-$ capacity is 1) and we know we cannot get from s to t without going through one of the vertices of the shortest path.

Max flow has size 1, therefore, the min cut has also size 1.

4) We use the min cut - either it will correspond to an edge in the original graph (OK, bomb out any of its vertices provided it is not s or t) or it will correspond to a vertex (obvious).

share|improve this answer

Hint: Prove that $s$ and $t$ do not belong to the same biconnected component of $G$.

share|improve this answer
1  
Further hint: For any two vertices $u$ and $v$ in the same connected bicomponent of $G$, there is a simple cycle in $G$ passing through both $u$ and $v$. –  user3533 Nov 8 '11 at 11:12

[this proof is incorrect as it stands]

Proof: Lay out the shortest path between s and t from left to right.

Assuming the vertex next to s does not satisfy the requirement for splitting s-t by deletion, then there must be an alternate path around it. This alternate path can be disjoint, from the path we already have. But we have the shortest path, so the alternate path must be just as long with different vertices. This cannot be since our path uses more than half the vertices. Thus we conclude that the alternate path must join up with our shortest path at some point, say vertex u.

Removing all the vertices from s to u in our and the alternate path, and using the fact that sub-paths of a shortest path stay shortest paths, we are left with a sub-problem which satisfies the exact same hypotheses we had for the original problem.

Continuing this reduction, we arrive at a point where the next vertex will in fact be one whose deletion will separate the graph.

share|improve this answer
    
Really? Does your new subproblem satisfy that the length of the shortest path between the two verticies is more than half of the vertices of the whole graph? –  jpalecek Nov 8 '11 at 11:08
    
oops. you are correct. –  David Gonzales Nov 8 '11 at 11:21

Your Answer

 
discard

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.