Prove that the graph on the respective unions of the vertex and edge sets of two connected graphs with exactly one common vertex is also connected

Question

Let $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ be connected graphs such that $V_1 \cap V_2 = \{v_0\}$, i.e., the two vertex sets have one common vertex $v_0$.

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.

Intuitively this seems obvious, if not trivial, but I'm unsure if I have correctly formalized my intuition (admittedly, my solution is rather wordy) or that I've adequately used the two definitions.

My solution:

Let $G_3 = (V, E)$ be a graph, and let $v_0 ∈ V$. WTS that there is a path between all pairs of vertices in $G_3$, eg, ∀ $u, v ∈ V, u$ and $v$ are connected.

We know that there is a path between every pair of vertices in $G_1$. We also know the same for $G_2$.

Let $u$ and $v$ be any two vertices in $G_3$. Now there are two cases: $u,v∈Vi, i=1,2$, and (without loss of generality) $u∈V1, v∈V2$. In the first case, we know from our assumption that all the vertices in V1 and V2 are connected. In the second case, because V1 and V2 share a common vertex, any vertex in G1 is also connected to any vertex in G2.

Therefore there is a path of vertices between every pair of vertices in $G_3$. Equivalently, every pair of vertices in $G_3$ is connected. Thus, $G_3$ is a connected graph.

Thanks everyone.

Answer 1

Let $u$ and $v$ be any two vertices in $G_3$. Now there are two cases: $u,v \in V_i,i=1,2$, and (without loss of generality) $u\in V_1, v\in V_2$.

That is a highly confusing wording. Separate cases do not hold at the same time, so "and" is not the connector to use between them. It took me some time to realize what you actually meant. Try something like this:

• "There are two cases: either both $u, v$ are in the same vertex set $V_1$ or $V_2$, or else $u$ and $v$ are in different sets - without loss of generality, $u \in V_1$ and $v \in V_2$.

In the first case, we know from our assumption that all the vertices in $V_1$ and $V_2$ are connected.

We know they are connected in $G_1$ and in $G_2$ respectively. Don't just assume your reader is going to immediately understand why this means that they are also connected in $G_3$. A single sentence is all that is required to make sure your reader sees the point. For example:

• Since $G_3$ contains every edge of $G_1$ and $G_2$, the same paths exist in $G_3$.

In the second case, because $V_1$ and $V_2$ share a common vertex, any vertex in $G_1$ is also connected to any vertex in $G_2$.

Why? This is the actual statement you are supposed to prove. Simply stating it does not constitute a proof.

Therefore there is a path of vertices between every pair of vertices in $G_3$ . Equivalently, every pair of vertices in $G_3$ is connected. Thus, $G_3$ is a connected graph.

I assume you meant "a path of edges", but either way, just saying "there is a path between every pair of vertices" would be better. If they don't already know what a path is, they are not going to understand your proof anyway.

And "Equivalently, every pair of vertices in $G_3$ is connected." serves absolutely no purpose here. you should get rid of it.