How to Show a graph is 3-connected?Proving a simple connected graph is a tree if adding an edge between two existing vertices of T creates exactly one cycleGraph theory based on k-connected graph on Menger's TheoremProof for corollary of non-separable graph3-connected graphs simple question$G^k$ is $k$-connectedGraph Theory :-Bi connected GraphProve that $G$ has $k$ pairwise disjoint $S$,$T,$ Paths?Finding vertex-cut using Menger's theorem3-Points on 3-vertex connected graphStrengthening of Menger's Theorem
Can I say "fingers" when referring to toes?
If A is dense in Q, then it must be dense in R.
Why can't the Brexit deadlock in the UK parliament be solved with a plurality vote?
Animation: customize bounce interpolation
Personal or impersonal in a technical resume
How to understand "he realized a split second too late was also a mistake"
Pre-Employment Background Check With Consent For Future Checks
Confusion over Hunter with Crossbow Expert and Giant Killer
Do you waste sorcery points if you try to apply metamagic to a spell from a scroll but fail to cast it?
How can I, as DM, avoid the Conga Line of Death occurring when implementing some form of flanking rule?
How to I force windows to use a specific version of SQLCMD?
I'm just a whisper. Who am I?
Review your own paper in Mathematics
Is there a distance limit for minecart tracks?
How do you justify more code being written by following clean code practices?
The Digit Triangles
When and why was runway 07/25 at Kai Tak removed?
Sound waves in different octaves
What's the name of the logical fallacy where a debater extends a statement far beyond the original statement to make it true?
If Captain Marvel (MCU) were to have a child with a human male, would the child be human or Kree?
Quoting Keynes in a lecture
Showing mass murder in a kid's book
"Oh no!" in Latin
ContourPlot — How do I color by contour curvature?
How to Show a graph is 3-connected?
Proving a simple connected graph is a tree if adding an edge between two existing vertices of T creates exactly one cycleGraph theory based on k-connected graph on Menger's TheoremProof for corollary of non-separable graph3-connected graphs simple question$G^k$ is $k$-connectedGraph Theory :-Bi connected GraphProve that $G$ has $k$ pairwise disjoint $S$,$T,$ Paths?Finding vertex-cut using Menger's theorem3-Points on 3-vertex connected graphStrengthening of Menger's Theorem
$begingroup$
I am attempting to solve a proof given in class which states the following:
A cubic tree is a tree whose vertices have degree either 1 or 3. Let T be a cubic tree and let G be a cubic graph obtained from T by adding a cycle through the leaves of T.
Show that G is 3-connected
The way I have attempted it to formulate my proof so far is supposing I have a cubic graph that was obtained from adding a cycle through the leaves of T. I also stated that Whitneys theorem tells us that that if the graph has 3 pairwise internally disjoint uv-paths then it must be 3 connected. So I begin attempting to show the graph has 3 pairwise disjoint uv-paths and this is where my logic gets lost. I started off by letting u,v by any two vertices in my cubic Graph G, and I also let P1,P2,P3 be three seperate paths in G. If I am somehow able to prove that each path is unique and only share u and v in common then I will have proved the result. So the problem lies in my way of going about showing each path is unique. Any hints?
combinatorics discrete-mathematics graph-theory trees graph-connectivity
New contributor
Bob is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
I am attempting to solve a proof given in class which states the following:
A cubic tree is a tree whose vertices have degree either 1 or 3. Let T be a cubic tree and let G be a cubic graph obtained from T by adding a cycle through the leaves of T.
Show that G is 3-connected
The way I have attempted it to formulate my proof so far is supposing I have a cubic graph that was obtained from adding a cycle through the leaves of T. I also stated that Whitneys theorem tells us that that if the graph has 3 pairwise internally disjoint uv-paths then it must be 3 connected. So I begin attempting to show the graph has 3 pairwise disjoint uv-paths and this is where my logic gets lost. I started off by letting u,v by any two vertices in my cubic Graph G, and I also let P1,P2,P3 be three seperate paths in G. If I am somehow able to prove that each path is unique and only share u and v in common then I will have proved the result. So the problem lies in my way of going about showing each path is unique. Any hints?
combinatorics discrete-mathematics graph-theory trees graph-connectivity
New contributor
Bob is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
$begingroup$
Welcome to Mathematics Stack Exchange! Take the short tour to see how how to get the most from your time here. For typesetting equations please use MathJax.
$endgroup$
– dantopa
Mar 14 at 5:37
$begingroup$
Users with enough points to see deleted posts will note that the same question was asked by another user just hours ago, math.stackexchange.com/questions/3147422/g-is-3-connected
$endgroup$
– Gerry Myerson
Mar 14 at 6:31
add a comment |
$begingroup$
I am attempting to solve a proof given in class which states the following:
A cubic tree is a tree whose vertices have degree either 1 or 3. Let T be a cubic tree and let G be a cubic graph obtained from T by adding a cycle through the leaves of T.
Show that G is 3-connected
The way I have attempted it to formulate my proof so far is supposing I have a cubic graph that was obtained from adding a cycle through the leaves of T. I also stated that Whitneys theorem tells us that that if the graph has 3 pairwise internally disjoint uv-paths then it must be 3 connected. So I begin attempting to show the graph has 3 pairwise disjoint uv-paths and this is where my logic gets lost. I started off by letting u,v by any two vertices in my cubic Graph G, and I also let P1,P2,P3 be three seperate paths in G. If I am somehow able to prove that each path is unique and only share u and v in common then I will have proved the result. So the problem lies in my way of going about showing each path is unique. Any hints?
combinatorics discrete-mathematics graph-theory trees graph-connectivity
New contributor
Bob is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
I am attempting to solve a proof given in class which states the following:
A cubic tree is a tree whose vertices have degree either 1 or 3. Let T be a cubic tree and let G be a cubic graph obtained from T by adding a cycle through the leaves of T.
Show that G is 3-connected
The way I have attempted it to formulate my proof so far is supposing I have a cubic graph that was obtained from adding a cycle through the leaves of T. I also stated that Whitneys theorem tells us that that if the graph has 3 pairwise internally disjoint uv-paths then it must be 3 connected. So I begin attempting to show the graph has 3 pairwise disjoint uv-paths and this is where my logic gets lost. I started off by letting u,v by any two vertices in my cubic Graph G, and I also let P1,P2,P3 be three seperate paths in G. If I am somehow able to prove that each path is unique and only share u and v in common then I will have proved the result. So the problem lies in my way of going about showing each path is unique. Any hints?
combinatorics discrete-mathematics graph-theory trees graph-connectivity
combinatorics discrete-mathematics graph-theory trees graph-connectivity
New contributor
Bob is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Bob is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Mar 14 at 6:09
Yanior Weg
2,54111346
2,54111346
New contributor
Bob is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Mar 14 at 5:34
BobBob
31
31
New contributor
Bob is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Bob is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Bob is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$begingroup$
Welcome to Mathematics Stack Exchange! Take the short tour to see how how to get the most from your time here. For typesetting equations please use MathJax.
$endgroup$
– dantopa
Mar 14 at 5:37
$begingroup$
Users with enough points to see deleted posts will note that the same question was asked by another user just hours ago, math.stackexchange.com/questions/3147422/g-is-3-connected
$endgroup$
– Gerry Myerson
Mar 14 at 6:31
add a comment |
$begingroup$
Welcome to Mathematics Stack Exchange! Take the short tour to see how how to get the most from your time here. For typesetting equations please use MathJax.
$endgroup$
– dantopa
Mar 14 at 5:37
$begingroup$
Users with enough points to see deleted posts will note that the same question was asked by another user just hours ago, math.stackexchange.com/questions/3147422/g-is-3-connected
$endgroup$
– Gerry Myerson
Mar 14 at 6:31
$begingroup$
Welcome to Mathematics Stack Exchange! Take the short tour to see how how to get the most from your time here. For typesetting equations please use MathJax.
$endgroup$
– dantopa
Mar 14 at 5:37
$begingroup$
Welcome to Mathematics Stack Exchange! Take the short tour to see how how to get the most from your time here. For typesetting equations please use MathJax.
$endgroup$
– dantopa
Mar 14 at 5:37
$begingroup$
Users with enough points to see deleted posts will note that the same question was asked by another user just hours ago, math.stackexchange.com/questions/3147422/g-is-3-connected
$endgroup$
– Gerry Myerson
Mar 14 at 6:31
$begingroup$
Users with enough points to see deleted posts will note that the same question was asked by another user just hours ago, math.stackexchange.com/questions/3147422/g-is-3-connected
$endgroup$
– Gerry Myerson
Mar 14 at 6:31
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
If $u,v$ are both leaves of $T$, the desired property holds: There is one path within $T$ and two paths within the added cycle, obviously edge-disjoint.
For general $u,v$: First, we have the unique path $gamma$ connecting $u$ and $v$ within $T$. If $u$ is not a leaf of $T$, we can start two paths from $u$ along its other two edges in $T$ and then continue these arbitrarily until a leaf. This gives two edge disjoint paths $gamma_u,1$, $gamma_u,2$ (also edge-disjoint to $gamma$) from $u$ to some leaves $u'_1$, $u'_2$ of $T$. If $u$ is a already a leaf, then we can take $gamma_u,1=gamma_u,2=$empty path (and $u'_1=u'_2=u$).
Do the same for $v$, resulting in $gamma_v,1$, $gamma_v,2$, $v_1'$, $v_2'$.
In the added circle, we can find edge-disjoint paths either from $u_1'$ to $v_1'$ and $u_2'$ to $v_2'$ or from $u_1'$ to $v_2'$ and $u_2'$ to $v_1'$. Together with the $gamma_u,i$, $gamma_v,i$, these form the desired paths.
$endgroup$
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
);
);
Bob is a new contributor. Be nice, and check out our Code of Conduct.
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%2f3147595%2fhow-to-show-a-graph-is-3-connected%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$
If $u,v$ are both leaves of $T$, the desired property holds: There is one path within $T$ and two paths within the added cycle, obviously edge-disjoint.
For general $u,v$: First, we have the unique path $gamma$ connecting $u$ and $v$ within $T$. If $u$ is not a leaf of $T$, we can start two paths from $u$ along its other two edges in $T$ and then continue these arbitrarily until a leaf. This gives two edge disjoint paths $gamma_u,1$, $gamma_u,2$ (also edge-disjoint to $gamma$) from $u$ to some leaves $u'_1$, $u'_2$ of $T$. If $u$ is a already a leaf, then we can take $gamma_u,1=gamma_u,2=$empty path (and $u'_1=u'_2=u$).
Do the same for $v$, resulting in $gamma_v,1$, $gamma_v,2$, $v_1'$, $v_2'$.
In the added circle, we can find edge-disjoint paths either from $u_1'$ to $v_1'$ and $u_2'$ to $v_2'$ or from $u_1'$ to $v_2'$ and $u_2'$ to $v_1'$. Together with the $gamma_u,i$, $gamma_v,i$, these form the desired paths.
$endgroup$
add a comment |
$begingroup$
If $u,v$ are both leaves of $T$, the desired property holds: There is one path within $T$ and two paths within the added cycle, obviously edge-disjoint.
For general $u,v$: First, we have the unique path $gamma$ connecting $u$ and $v$ within $T$. If $u$ is not a leaf of $T$, we can start two paths from $u$ along its other two edges in $T$ and then continue these arbitrarily until a leaf. This gives two edge disjoint paths $gamma_u,1$, $gamma_u,2$ (also edge-disjoint to $gamma$) from $u$ to some leaves $u'_1$, $u'_2$ of $T$. If $u$ is a already a leaf, then we can take $gamma_u,1=gamma_u,2=$empty path (and $u'_1=u'_2=u$).
Do the same for $v$, resulting in $gamma_v,1$, $gamma_v,2$, $v_1'$, $v_2'$.
In the added circle, we can find edge-disjoint paths either from $u_1'$ to $v_1'$ and $u_2'$ to $v_2'$ or from $u_1'$ to $v_2'$ and $u_2'$ to $v_1'$. Together with the $gamma_u,i$, $gamma_v,i$, these form the desired paths.
$endgroup$
add a comment |
$begingroup$
If $u,v$ are both leaves of $T$, the desired property holds: There is one path within $T$ and two paths within the added cycle, obviously edge-disjoint.
For general $u,v$: First, we have the unique path $gamma$ connecting $u$ and $v$ within $T$. If $u$ is not a leaf of $T$, we can start two paths from $u$ along its other two edges in $T$ and then continue these arbitrarily until a leaf. This gives two edge disjoint paths $gamma_u,1$, $gamma_u,2$ (also edge-disjoint to $gamma$) from $u$ to some leaves $u'_1$, $u'_2$ of $T$. If $u$ is a already a leaf, then we can take $gamma_u,1=gamma_u,2=$empty path (and $u'_1=u'_2=u$).
Do the same for $v$, resulting in $gamma_v,1$, $gamma_v,2$, $v_1'$, $v_2'$.
In the added circle, we can find edge-disjoint paths either from $u_1'$ to $v_1'$ and $u_2'$ to $v_2'$ or from $u_1'$ to $v_2'$ and $u_2'$ to $v_1'$. Together with the $gamma_u,i$, $gamma_v,i$, these form the desired paths.
$endgroup$
If $u,v$ are both leaves of $T$, the desired property holds: There is one path within $T$ and two paths within the added cycle, obviously edge-disjoint.
For general $u,v$: First, we have the unique path $gamma$ connecting $u$ and $v$ within $T$. If $u$ is not a leaf of $T$, we can start two paths from $u$ along its other two edges in $T$ and then continue these arbitrarily until a leaf. This gives two edge disjoint paths $gamma_u,1$, $gamma_u,2$ (also edge-disjoint to $gamma$) from $u$ to some leaves $u'_1$, $u'_2$ of $T$. If $u$ is a already a leaf, then we can take $gamma_u,1=gamma_u,2=$empty path (and $u'_1=u'_2=u$).
Do the same for $v$, resulting in $gamma_v,1$, $gamma_v,2$, $v_1'$, $v_2'$.
In the added circle, we can find edge-disjoint paths either from $u_1'$ to $v_1'$ and $u_2'$ to $v_2'$ or from $u_1'$ to $v_2'$ and $u_2'$ to $v_1'$. Together with the $gamma_u,i$, $gamma_v,i$, these form the desired paths.
answered Mar 14 at 5:49
Hagen von EitzenHagen von Eitzen
283k23272507
283k23272507
add a comment |
add a comment |
Bob is a new contributor. Be nice, and check out our Code of Conduct.
Bob is a new contributor. Be nice, and check out our Code of Conduct.
Bob is a new contributor. Be nice, and check out our Code of Conduct.
Bob is a new contributor. Be nice, and check out our Code of Conduct.
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%2f3147595%2fhow-to-show-a-graph-is-3-connected%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$
Welcome to Mathematics Stack Exchange! Take the short tour to see how how to get the most from your time here. For typesetting equations please use MathJax.
$endgroup$
– dantopa
Mar 14 at 5:37
$begingroup$
Users with enough points to see deleted posts will note that the same question was asked by another user just hours ago, math.stackexchange.com/questions/3147422/g-is-3-connected
$endgroup$
– Gerry Myerson
Mar 14 at 6:31