0
$\begingroup$

Let $G = (V, E)$ be a connected weighted graph. Assume the weights are distinct. Let $V_1, V_2, . . . , V_p$ be a partition of V into two or more nonempty parts.

For each $i (1 ≤ i ≤ p)$, let ei be the minimum weight edge within the set of all edges with one endpoint in Vi and the other in $V − V_i$ . Call such an edge a super-edge.

(a) Prove that for each i such a super-edge ei exists.

Define a new graph S whose vertices are the parts $V_i$ (so S has p vertices), and two parts are connected iff there a super-edge between them.

(b) Prove that S is a forest. (c) Prove that S has at most p/2 components.

For problem a, is it because ei contains in the minimum spanning tree? for problem b, I think we should have a cycle whose both edges are super-edge and get contradiction? I have no idea how to do c.

This is a long problem, Could someone help me ?

$\endgroup$
1
$\begingroup$

Hints: For (a), start with any vertex $u\in V_i$ and any vertex $v\in V-V_i$. Since $G$ is connected, there must be a path from $u$ to $v$, consisting of vertices $x_0, \dots, x_k \in V$, where $x_0=u$ and $x_k=v$. Consider the maximum $k$ for which $x_k$ is in $V_i$.

For (b), it may be helpful to consider the directed graph $S'$ which is defined the same as $S$ but keeping track of which direction the super-edges go (i.e., given an edge which has minimum weight within the set of edges with one endpoint in $V_i$ and the other in $V-V_i$, we include $e_i$ in $S'$ as a directed edge from $V_i$ to the other part.) Notice that by definition, each vertex in $S'$ has a unique edge coming out of it (but it may have more than one edge coming into it, or none at all). Suppose that we have a cycle $C$ in $S$, and consider a corresponding subgraph $C'$ of $S'$ (Such a corresponding subgraph may not be unique, because a single edge $e_i$ in $S$ could possibly correspond to a pair of edges in $S'$, one going in each direction; to form $C'$, in such a case just choose one of these two edges arbitrarily.). Each vertex $x$ in $C'$ has at most one edge coming out of it in $C'$ (since it has at most one edge coming out of it in $S'$), and yet the total number of edges coming out and coming in is 2 since $C$ is a cycle, and this means that each vertex $x$ in $C'$ has at least one edge coming in. Follow these edges back step-by-step, and we find a directed cycle contained inside $C'$. At the same time, as we follow these edges back, show that at each step the weight of the edge strictly increases, which creates a contradiction.

For part (c), think about what is the minimum possible size of a component of $S$.

$\endgroup$
  • $\begingroup$ Thanks for your detailed answer, but how to do do part b without using directed graph? $\endgroup$ – ZHJ Feb 24 '15 at 16:21
  • $\begingroup$ Maybe I'm overlooking something, but I'm not seeing a way to do it without essentially using directed graphs. To get a contradiction from having a cycle, we need the edges to be going around in the same direction, which is not something that can be described in terms of the undirected graph. $\endgroup$ – Brent Kerby Feb 24 '15 at 16:45
1
$\begingroup$

For (a) you know that each $V_i$ is non empty and that $V-V_i$ is also non empty (since there is at least two non empty part in the partition). Since $G$ is connected there must be a path between any two vertices, hence there is an edge between any two non empty set of vertices. And since all the weight are distinct there is only one which is minimal. Hence the existence of $e_i$.

For (b), as you said, assume that there is a cycle in $S$. Hint the minimality of the $e_i$ will get you a contradiction with the cycle.

Edit: Look only if you are really stuck

Notice that an edge connecting $V_i$ and $V_j$ is either the super edge $e_i$ or $e_j$. Assume that you have a cycle $V_1,..,V_n$ and denote $E_i=(V_i,V_{i+1})$ the edge connecting $V_i$ and $V_{i+1}$ in the cycle (note that here and in the following I assume that n+1=1 to simplify notations). There are three possible cases: 1) $\forall i, E_i=e_i$, 2) $\forall i, E_i=e_{i+1}$, 3) $\exists i, E_i\neq e_i$ and $E_{i-1}\neq e_i$

Now that we have a case distinctions here are the answer for each cases: Case1:

since the $e_i$ are minimal we know that $E_i>E_{i+1}$ and propagating this inequality we obtain $E_1>E_1$ contradiction.

Case2:

Similarly to case 1, we have $E_{i+1}>E_i$ and again we get $E_1>E_1$. Contradiction.

Case3:

$\exists i, E_i\neq e_i$ and $E_{i-1}\neq e_i$ but since there is $n$ $E_i$ and $n$ $V_i$ in the cycle that mean one of the $E_i$ is not a super edge. Contradiction with the definition of S.

For (c), assume that you have more than $p/2$ components. Since there are $p$ vertices in $S$ that means there is a vertex that is not connected to any other. Explain why it is not possible.

$\endgroup$
  • $\begingroup$ Hello, I do not understand why there is a vertex is not connected to any other, could you explain more detailedly? $\endgroup$ – ZHJ Feb 24 '15 at 15:51
  • $\begingroup$ If you have p/2+k components in your forest (with k>0) and two vertices by components you have p+2k vertices. Contradiction with "there are p vertices". $\endgroup$ – wece Feb 24 '15 at 15:54
  • $\begingroup$ Is that clearer now? $\endgroup$ – wece Feb 24 '15 at 15:55
  • $\begingroup$ is this a thm that we have component of the forest then we have 2n vertices? Why? $\endgroup$ – ZHJ Feb 24 '15 at 15:59
  • $\begingroup$ It is not a thm. It's just a remark. If you have a forest of 2n vertices and more than n components in the forest than necessarily at least one of the component is a single vertex. $\endgroup$ – wece Feb 24 '15 at 16:02

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.