1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How did you try to prove this and what problem did you face in that? $\endgroup$ – M. Vinay Mar 23 at 16:04
  • $\begingroup$ @M.Vinay I'm not sure how to formalize my intuition into logic. Please check my updated question. $\endgroup$ – Tameem Hassan Mar 23 at 16:43
  • $\begingroup$ It's essentially correct. If you want the proof to appear more rigorous, say something like "Let $u$ and $v$ be any two vertices in $G_3$. Now there are three cases: $u, v \in V_1$, $u,v \in V_2$, and (without loss of generality) $u \in V_1$, $v \in V_2$." And clearly argue that in each case, there is a path from $u$ to $v$. In fact the first two cases can be argued together (rewrite that to $u, v \in V_i$, $i = 1, 2$), since the logic is the same. $\endgroup$ – M. Vinay Mar 23 at 17:07
  • $\begingroup$ @Somos The question already provides an edge set for which we have to prove the connectedness. Doesn't joining vertices by a new edge add an edge to the given edge set? $\endgroup$ – Tameem Hassan Mar 23 at 18:18
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Ah, it's my fault for writing it that way in the comments (about the different cases), where I was trying to keep it brief, and was sure OP would understand what I meant. $\endgroup$ – M. Vinay Mar 24 at 3:14
  • $\begingroup$ @M.Vinay - I saw where it came from, but yours was just a comment to give the idea. Tameem Hassan is the one who stated it that way in the proof. And he needs to figure out how to clearly state things if he wants to write convincing proofs. That is why I always include comments about how to improve the wording on proof-verification questions, as well as addressing the logic. $\endgroup$ – Paul Sinclair Mar 24 at 15:11

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.