Let $G = (V,E)$ be a graph and let $H_1 = (V_1,E_1)$ and $H_2 = (V_2,E_2)$ be two connected subgraphs of $G$ that have at least one node in common. Prove that the graph $H = H_1\cup H_2 = (V_1\cup V_2,E_1\cup E_2)$ is connected.

Pick a random node $V_i$ in $H_1 \cup H_2$. Since $H_1$ is connected, I can reach from $V_i$ to the common node of $H_1$ and $H_2$. Since $H_2$ is connected, I can reach from $V_i$ to nodes in $H_2$. Thus, $H_1\cup H_2$ is connected. Is this the correct logic? How do I write it out formally?

  • 1
    $\begingroup$ One options is pick two arbitrary vertices, and describe a path connecting them in terms of the paths guaranteed to exist by hypothesis. $\endgroup$ – Travis Sep 8 '14 at 6:32
  • $\begingroup$ So choose two random vertices, each from the H1 and H2. Since both H1 and H2 are connected, I can reach from the two random vertices to the common vertex in H1 and H2. So the union of H1 and H2 are connected in this way? $\endgroup$ – holidayeveryday Sep 8 '14 at 6:52
  • $\begingroup$ In principle you must show that this works for any two vertices, not just one from each of $H_1$ and $H_2$. It's trivial to handle the remaining cases but you can also handle all of these cases at once. How do you describe a sequence of a edges that connects $H_1$ to $H_2$? $\endgroup$ – Travis Sep 8 '14 at 7:09

given two vertices $a,b$ in $H$, we have to show that they are connected by a path. they either lie in the same component $H_i$, in which case this follows from the connectedness of $H_i$. Or they lie in different $H_i$ but in this case we can construct a path from $a$ to $b$ by concatenation of the two paths from $a$ to $x$ and $x$ to $b$ resp., where $x$ is a common vertex. The existence of those two paths follows again from the connectedness of the $H_i$.

One could prove this in less lines by using that path connectedness of two points is an equivalence relation, in particular transitive. The same result holds for topological spaces.


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.