Let H = (V,E) be a connected, undirected graph. Let A be a subset of E. Let C = (W , F) be a connected component (tree) in the forest G = (V,A). Let (u,v) be an edge connecting C to some other component in G.

Now doesnt it imply that (u,v) must belong to A since it is in forest G and it doesnot matter which component it connects? Is this proof wrong:

For purpose of contradiction lets assume that it does not belong to A. As (u,v) connects two components of graph it must be an edge. As Set of edge is given by A in graph G it must belong to A which contradict our assumption.

  • $\begingroup$ A is a subset of the graph edges. So why do you think there cannot be an edge in E which is not in A? $\endgroup$
    – rici
    Commented May 13, 2016 at 19:45
  • $\begingroup$ @rici It cannot be in E as the edge connects components in graph G NOT in H. And set of edge of G is given by A. $\endgroup$ Commented May 14, 2016 at 2:08

1 Answer 1


Here's a simple example. Let $H$ have vertices $V=\{1,2,3,4\}$ and edges $E=\{(1,2),(2,3),(3,4),(4,1),(1,3)\}$, so $H$ is a square plus one diagonal.

Now let $A=\{(2,3),(4,1)\}$, so these are the edges of $G$ and hence $G$ will have two components, each consisting of one edge of $A$. Let's pick $C$ to be the component consisting of $\{2,3\}$, so the other component will be $(4,1)$.

There is an edge of $H$ connecting these two components, namely $(1,3)$. Your mistake was assuming that the $(u,v)$ edge was in the forest $G$. If it were, then it would have to lie in a single component so couldn't connect two components of $G$.

  • $\begingroup$ I am not assuming it was edge in forest G. It is given that it is an edge in forest G. $\endgroup$ Commented May 14, 2016 at 2:03
  • $\begingroup$ The line is Let (u,v) be an edge connecting C to some other component in G. $\endgroup$ Commented May 14, 2016 at 2:17
  • $\begingroup$ It connects in G $\endgroup$ Commented May 14, 2016 at 2:29
  • 1
    $\begingroup$ @AbhinavGarg. Nowhere does it say that $(u,v)$ must be in $G$. If that were the case, then $(u,v)$ couldn't possibly connect two (different) components. $\endgroup$ Commented May 14, 2016 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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