# Prove that the graph $H = H_1\cup H_2 = (V_1\cup V_2,E_1\cup E_2)$ is connected.

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?

• One options is pick two arbitrary vertices, and describe a path connecting them in terms of the paths guaranteed to exist by hypothesis. – Travis Sep 8 '14 at 6:32
• 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? – holidayeveryday Sep 8 '14 at 6:52
• 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$? – 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$.