1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ If the intersection between both vertice sets had more than 1 vertex, how would this proof change? Would you take into account for duplicates? $\endgroup$ – neet Apr 9 at 19:21
  • $\begingroup$ @neet no, then you can pick any vertex of intersection you like. $\endgroup$ – Henno Brandsma Apr 9 at 19:23

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.