0
$\begingroup$

I'm attempting to prove the following with contradiction. Unfortunately i'm not sure if my deduction is flawless in this one.

Given: $G_1=(V_1,E_1),\quad G_2=(V_2,E_2),\quad G=(V_1\cup V_2,E_1\cup E_2)$

Prove that: $(V_1\cap V_2) \neq \emptyset$ if $G$ is connected.

Proof by contradiction:

Assume: $(V_1\cap V_2)=\emptyset $

Then $\forall v \in V_1$ and $w \in V_2$ exists a path between every pair of vertices $v$ and $w$. $\implies$ $G$ is connected $\implies$ (I'm not sure if I can already deduce it) $(V_1\cap V_2)\neq \emptyset$

Which contradicts the assumption.

I know the intersection can't be empty if G is connected. But I have no idea how I can express it in formal mathematical proof. Any help appreciated.

$\endgroup$

1 Answer 1

1
$\begingroup$

Okay. I already solved it.

Suppose: $V_1\cap V_2= \emptyset$ and $G$ is connected.

Then $\forall v\in V_1, w \in V_2$ exists a path between every pair of vertices $v$ and $w$.

$\implies v,w \in V_1 \wedge v,w \in V_2$

$\implies V_1 \cap V_2 \neq \emptyset $

$\endgroup$

You must log in to answer this question.

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