# What do we mean when we say an edge (u,v) connects some component to other component in forest G = (V,A)

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.

• 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?
– rici
May 13, 2016 at 19:45
• @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. May 14, 2016 at 2:08

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$.
• @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. May 14, 2016 at 19:56