3
$\begingroup$

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!

4 Answers 4

-1

I do not have enough reputation to post something in a comment so i would post it here. Thank you for your cooperation .

So my confusion is:

if we delete a vertex v:

v ∈ V - {s,t}  

from an undirected connected graph G = (V,E).

Can we prove that the deletion of v disconnects G?

4

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

  • 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$.2011-11-08
1

[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.

  • 0
    oops. you are correct.2011-11-08
1

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).