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

1 Answer 1

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$
3
  • $\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
    Commented Apr 9, 2019 at 19:21
  • $\begingroup$ @neet no, then you can pick any vertex of intersection you like. $\endgroup$ Commented Apr 9, 2019 at 19:23
  • $\begingroup$ @neet Recall that the person who asked can mark one answer as "accepted". See math.stackexchange.com/tour $\endgroup$
    – Robert Z
    Commented Jul 18, 2019 at 15:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .