0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\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
    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$
    – Abhinav Garg
    May 14, 2016 at 2:08

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ I am not assuming it was edge in forest G. It is given that it is an edge in forest G. $\endgroup$
    – Abhinav Garg
    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$
    – Abhinav Garg
    May 14, 2016 at 2:17
  • $\begingroup$ It connects in G $\endgroup$
    – Abhinav Garg
    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$
    – Rick Decker
    May 14, 2016 at 19:56

Your Answer

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

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