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 The 2019 Stack Overflow Developer Survey Results Are Inprove using the definition of connectedness and paths that $G_3 = (V_1cup V_2, E_1cup E_2)$ is a connected graphProve that the graph $H = H_1cup H_2 = (V_1cup V_2,E_1cup E_2)$ is connected.Prove that the graph is connectedThere are at least 2 vertex-disjoint paths between every pair of vertices?Graphs - connected graph with edge disjunctive cyclesGraph theory: Proof that if the graph G(V1V2,E1E2) is conntected then the intersection (V1V2) is not empty.How to denote the union operation of $n$ weighted graphs correctly?eulerian circuit combinatoricsProve, that relation $R(G,preccurlyeq_G) ; (G_1 preccurlyeq_G G_2: G_1 text is subgraph of G_2)$ is a PosetProve that the deletion of edges of a minimum-edge cut of a connected graph G results in a disconnected graph with exactly two components.Is every $f(k)$-vertex-connected graph the edge-disjoint union of two $k$-vertex-connected graphs?
What is the accessibility of a package's `Private` context variables?
How technical should a Scrum Master be to effectively remove impediments?
Can one be advised by a professor who is very far away?
How to answer pointed "are you quitting" questioning when I don't want them to suspect
Is bread bad for ducks?
Does the shape of a die affect the probability of a number being rolled?
Is flight data recorder erased after every flight?
The difference between dialogue marks
Can a flute soloist sit?
Output the Arecibo Message
Did Section 31 appear in Star Trek: The Next Generation?
Identify boardgame from Big movie
Why hard-Brexiteers don't insist on a hard border to prevent illegal immigration after Brexit?
Why isn't the circumferential light around the M87 black hole's event horizon symmetric?
What are the motivations for publishing new editions of an existing textbook, beyond new discoveries in a field?
Multiply Two Integer Polynomials
Worn-tile Scrabble
Write faster on AT24C32
Origin of "cooter" meaning "vagina"
Are there incongruent pythagorean triangles with the same perimeter and same area?
One word riddle: Vowel in the middle
What to do when moving next to a bird sanctuary with a loosely-domesticated cat?
What is the meaning of the verb "bear" in this context?
Did Scotland spend $250,000 for the slogan "Welcome to Scotland"?
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
The 2019 Stack Overflow Developer Survey Results Are Inprove using the definition of connectedness and paths that $G_3 = (V_1cup V_2, E_1cup E_2)$ is a connected graphProve that the graph $H = H_1cup H_2 = (V_1cup V_2,E_1cup E_2)$ is connected.Prove that the graph is connectedThere are at least 2 vertex-disjoint paths between every pair of vertices?Graphs - connected graph with edge disjunctive cyclesGraph theory: Proof that if the graph G(V1V2,E1E2) is conntected then the intersection (V1V2) is not empty.How to denote the union operation of $n$ weighted graphs correctly?eulerian circuit combinatoricsProve, that relation $R(G,preccurlyeq_G) ; (G_1 preccurlyeq_G G_2: G_1 text is subgraph of G_2)$ is a PosetProve that the deletion of edges of a minimum-edge cut of a connected graph G results in a disconnected graph with exactly two components.Is every $f(k)$-vertex-connected graph the edge-disjoint union of two $k$-vertex-connected graphs?
$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.
graph-theory
asked Mar 23 at 15:51
Tameem HassanTameem Hassan
93
$endgroup$
add a comment |
$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.
graph-theory
asked Mar 23 at 15:51
Tameem HassanTameem Hassan
93
$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
add a comment |
$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.
graph-theory
asked Mar 23 at 15:51
Tameem HassanTameem Hassan
93
$endgroup$
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.
graph-theory
graph-theory
asked Mar 23 at 15:51
Tameem HassanTameem Hassan
93
asked Mar 23 at 15:51
Tameem HassanTameem Hassan
93
edited Mar 23 at 20:17
Tameem Hassan
asked Mar 23 at 15:51
Tameem HassanTameem Hassan
93
asked Mar 23 at 15:51
Tameem HassanTameem Hassan
93
asked Mar 23 at 15:51
Tameem HassanTameem Hassan
93
93
$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
add a comment |
$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
$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$
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$
@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$
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
$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
add a comment |
1 Answer
1
active
oldest
votes
$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) $uin V_1, vin 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.
answered Mar 24 at 1:28
Paul SinclairPaul Sinclair
20.8k21543
$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
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3159468%2fprove-that-the-graph-on-the-respective-unions-of-the-vertex-and-edge-sets-of-two%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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) $uin V_1, vin 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.
answered Mar 24 at 1:28
Paul SinclairPaul Sinclair
20.8k21543
$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
add a comment |
$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) $uin V_1, vin 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.
answered Mar 24 at 1:28
Paul SinclairPaul Sinclair
20.8k21543
$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
add a comment |
$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) $uin V_1, vin 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.
answered Mar 24 at 1:28
Paul SinclairPaul Sinclair
20.8k21543
$endgroup$
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) $uin V_1, vin 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.
answered Mar 24 at 1:28
Paul SinclairPaul Sinclair
20.8k21543
answered Mar 24 at 1:28
Paul SinclairPaul Sinclair
20.8k21543
answered Mar 24 at 1:28
Paul SinclairPaul Sinclair
20.8k21543
answered Mar 24 at 1:28
Paul SinclairPaul Sinclair
20.8k21543
20.8k21543
$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
add a comment |
$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
$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$
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
$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
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3159468%2fprove-that-the-graph-on-the-respective-unions-of-the-vertex-and-edge-sets-of-two%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$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