# prove using the definition of connectedness and paths that $G_3 = (V_1\cup V_2, E_1\cup E_2)$ is a connected graph

Let $$G_1 = (V_1, E_1), G_2 = (V_2, E_2)$$ such that...

• G1 is connected
• G2 is connected
• $$V_1\cap V_2={v_o}$$

I know since the intersection of both vertex sets only contains a single vertex, implying any path including vertices from $$G_1$$ and $$G_2$$ will not include duplicates. How do I formalize this notion to show every vertex in $$G_3$$ is connected to every other vertex (i.e.: there exists a path between every other vertex).

• For a vertex $u$ and $w$ in $G_3$, if both vertices are in $G_1$ or both are in $G_2$, then this is obvious. If $u$ is in $G_1$ and $w$ in $G_2$, there is a path joining $u$ and $v$ in $G_1$ and a path joining $v$ and $w$ in $G_2$ so there is a path joining $u$ and $w$ in $G_3$ via $v$. – PJK Apr 9 at 4:05
• you used union instead of intersection for the third constraint. – mathpadawan Apr 9 at 4:16
• @mathpadawan fixed! – neet Apr 9 at 5:42
• – M. Vinay Apr 9 at 6:04

Let $$u$$ and $$v$$ in $$V_3=V_1 \cup V_2$$. If $$u,v$$ are both in $$V_1$$, then there is a path from $$u$$ to $$v$$ in $$(V_1,E_1)$$ and this is still a path from $$u$$ to $$v$$ in $$(V_3,E_3)$$ (as $$E_1 \subseteq E_3$$).
If $$u,v$$ are both in $$V_2$$, mutatis mutandis the same argument applies in $$(V_2,E_2)$$.
Finally we have (WLOG) $$u \in V_1$$, $$v \in V_2$$. Then there is a path from $$u$$ to $$v_0$$ in $$(V_1,E_1)$$ and a path from $$v_0$$ to $$v$$ in $$(V_2,E_2)$$. Combining these paths we have a path in $$(V_3,E_3)$$ from $$u$$ to $$v$$.