Prove a Graph $G$ Has Crossing number $Cr(G) = 5$
$begingroup$
In my graph theory class we've had several questions where we were to find the crossing number of a graph and prove our answer. In all of these questions, $Cr(G) = 1$, so we need only show a drawing of the graph with 1 crossing and that the graph is not planar either using one of the 2 common inequalities relating vertices ($q leq 3p - 6$ for any planar graph $q leq 2p - 4$ for a planar bipartite graph) or by edge and vertex contraction to find a resulting graph that contained either $K_{3,3}$ or $K_5$ (If either of these graphs were found, the graph is nonplanar by Kuratowski's Theorem).
I've come across a problem in my textbook where it asks the reader to prove that a graph has crossing number 5 and provides a picture (included below) that shows a drawing of the graph with exactly 5 crossings.
So, clearly $Cr(G) leq 5$ given the drawing, but to complete the proof I must show that $Cr(G) geq 5$, but I know only that I have been able to contract vertices and edges to find $K_{3,3}$ or $K_5 implies Cr(G) geq 1$. What should I do to show that the crossing number is $geq 5$?
Or, more generally how to show that $Cr(G) geq n, n in mathbb{N} - {1}$?
graph-theory planar-graph
asked Nov 25 '18 at 17:25
rjm27trekkierjm27trekkie
1219
$endgroup$
add a comment |
$begingroup$
In my graph theory class we've had several questions where we were to find the crossing number of a graph and prove our answer. In all of these questions, $Cr(G) = 1$, so we need only show a drawing of the graph with 1 crossing and that the graph is not planar either using one of the 2 common inequalities relating vertices ($q leq 3p - 6$ for any planar graph $q leq 2p - 4$ for a planar bipartite graph) or by edge and vertex contraction to find a resulting graph that contained either $K_{3,3}$ or $K_5$ (If either of these graphs were found, the graph is nonplanar by Kuratowski's Theorem).
I've come across a problem in my textbook where it asks the reader to prove that a graph has crossing number 5 and provides a picture (included below) that shows a drawing of the graph with exactly 5 crossings.
So, clearly $Cr(G) leq 5$ given the drawing, but to complete the proof I must show that $Cr(G) geq 5$, but I know only that I have been able to contract vertices and edges to find $K_{3,3}$ or $K_5 implies Cr(G) geq 1$. What should I do to show that the crossing number is $geq 5$?
Or, more generally how to show that $Cr(G) geq n, n in mathbb{N} - {1}$?
graph-theory planar-graph
asked Nov 25 '18 at 17:25
rjm27trekkierjm27trekkie
1219
$endgroup$
add a comment |
$begingroup$
In my graph theory class we've had several questions where we were to find the crossing number of a graph and prove our answer. In all of these questions, $Cr(G) = 1$, so we need only show a drawing of the graph with 1 crossing and that the graph is not planar either using one of the 2 common inequalities relating vertices ($q leq 3p - 6$ for any planar graph $q leq 2p - 4$ for a planar bipartite graph) or by edge and vertex contraction to find a resulting graph that contained either $K_{3,3}$ or $K_5$ (If either of these graphs were found, the graph is nonplanar by Kuratowski's Theorem).
I've come across a problem in my textbook where it asks the reader to prove that a graph has crossing number 5 and provides a picture (included below) that shows a drawing of the graph with exactly 5 crossings.
So, clearly $Cr(G) leq 5$ given the drawing, but to complete the proof I must show that $Cr(G) geq 5$, but I know only that I have been able to contract vertices and edges to find $K_{3,3}$ or $K_5 implies Cr(G) geq 1$. What should I do to show that the crossing number is $geq 5$?
Or, more generally how to show that $Cr(G) geq n, n in mathbb{N} - {1}$?
graph-theory planar-graph
asked Nov 25 '18 at 17:25
rjm27trekkierjm27trekkie
1219
$endgroup$
In my graph theory class we've had several questions where we were to find the crossing number of a graph and prove our answer. In all of these questions, $Cr(G) = 1$, so we need only show a drawing of the graph with 1 crossing and that the graph is not planar either using one of the 2 common inequalities relating vertices ($q leq 3p - 6$ for any planar graph $q leq 2p - 4$ for a planar bipartite graph) or by edge and vertex contraction to find a resulting graph that contained either $K_{3,3}$ or $K_5$ (If either of these graphs were found, the graph is nonplanar by Kuratowski's Theorem).
I've come across a problem in my textbook where it asks the reader to prove that a graph has crossing number 5 and provides a picture (included below) that shows a drawing of the graph with exactly 5 crossings.
So, clearly $Cr(G) leq 5$ given the drawing, but to complete the proof I must show that $Cr(G) geq 5$, but I know only that I have been able to contract vertices and edges to find $K_{3,3}$ or $K_5 implies Cr(G) geq 1$. What should I do to show that the crossing number is $geq 5$?
Or, more generally how to show that $Cr(G) geq n, n in mathbb{N} - {1}$?
graph-theory planar-graph
graph-theory planar-graph
asked Nov 25 '18 at 17:25
rjm27trekkierjm27trekkie
1219
asked Nov 25 '18 at 17:25
rjm27trekkierjm27trekkie
1219
asked Nov 25 '18 at 17:25
rjm27trekkierjm27trekkie
1219
asked Nov 25 '18 at 17:25
rjm27trekkierjm27trekkie
1219
asked Nov 25 '18 at 17:25
rjm27trekkierjm27trekkie
1219
1219
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
After further review I have found a proof as follows:
We have that $cr(G) leq 5$ given the drawing presented. If $cr(G) < 5$ then removing 4 edges may create a planar graph, but $forall$ planar graph we have $q leq 3p - 6$. Given $p=10, q=29$ in the graph shown we would then have $29-4=25 leq 3(10) - 6 = 24$, a contradiction. Thus $cr(G) geq 5$. Then, necessarily, $cr(G) = 5$. $square$
answered Nov 28 '18 at 0:00
rjm27trekkierjm27trekkie
1219
$endgroup$
$begingroup$
You mean $29-4$ instead of $29-5$ right? I think your proof works.
$endgroup$
– nafhgood
Nov 28 '18 at 13:47
$begingroup$
Yeah dunno how that got there. Fixed
$endgroup$
– rjm27trekkie
Nov 29 '18 at 15:44
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%2f3013116%2fprove-a-graph-g-has-crossing-number-crg-5%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$
After further review I have found a proof as follows:
We have that $cr(G) leq 5$ given the drawing presented. If $cr(G) < 5$ then removing 4 edges may create a planar graph, but $forall$ planar graph we have $q leq 3p - 6$. Given $p=10, q=29$ in the graph shown we would then have $29-4=25 leq 3(10) - 6 = 24$, a contradiction. Thus $cr(G) geq 5$. Then, necessarily, $cr(G) = 5$. $square$
answered Nov 28 '18 at 0:00
rjm27trekkierjm27trekkie
1219
$endgroup$
$begingroup$
You mean $29-4$ instead of $29-5$ right? I think your proof works.
$endgroup$
– nafhgood
Nov 28 '18 at 13:47
$begingroup$
Yeah dunno how that got there. Fixed
$endgroup$
– rjm27trekkie
Nov 29 '18 at 15:44
add a comment |
$begingroup$
After further review I have found a proof as follows:
We have that $cr(G) leq 5$ given the drawing presented. If $cr(G) < 5$ then removing 4 edges may create a planar graph, but $forall$ planar graph we have $q leq 3p - 6$. Given $p=10, q=29$ in the graph shown we would then have $29-4=25 leq 3(10) - 6 = 24$, a contradiction. Thus $cr(G) geq 5$. Then, necessarily, $cr(G) = 5$. $square$
answered Nov 28 '18 at 0:00
rjm27trekkierjm27trekkie
1219
$endgroup$
$begingroup$
You mean $29-4$ instead of $29-5$ right? I think your proof works.
$endgroup$
– nafhgood
Nov 28 '18 at 13:47
$begingroup$
Yeah dunno how that got there. Fixed
$endgroup$
– rjm27trekkie
Nov 29 '18 at 15:44
add a comment |
$begingroup$
After further review I have found a proof as follows:
We have that $cr(G) leq 5$ given the drawing presented. If $cr(G) < 5$ then removing 4 edges may create a planar graph, but $forall$ planar graph we have $q leq 3p - 6$. Given $p=10, q=29$ in the graph shown we would then have $29-4=25 leq 3(10) - 6 = 24$, a contradiction. Thus $cr(G) geq 5$. Then, necessarily, $cr(G) = 5$. $square$
answered Nov 28 '18 at 0:00
rjm27trekkierjm27trekkie
1219
$endgroup$
After further review I have found a proof as follows:
We have that $cr(G) leq 5$ given the drawing presented. If $cr(G) < 5$ then removing 4 edges may create a planar graph, but $forall$ planar graph we have $q leq 3p - 6$. Given $p=10, q=29$ in the graph shown we would then have $29-4=25 leq 3(10) - 6 = 24$, a contradiction. Thus $cr(G) geq 5$. Then, necessarily, $cr(G) = 5$. $square$
answered Nov 28 '18 at 0:00
rjm27trekkierjm27trekkie
1219
edited Nov 29 '18 at 15:44
answered Nov 28 '18 at 0:00
rjm27trekkierjm27trekkie
1219
answered Nov 28 '18 at 0:00
rjm27trekkierjm27trekkie
1219
answered Nov 28 '18 at 0:00
rjm27trekkierjm27trekkie
1219
1219
$begingroup$
You mean $29-4$ instead of $29-5$ right? I think your proof works.
$endgroup$
– nafhgood
Nov 28 '18 at 13:47
$begingroup$
Yeah dunno how that got there. Fixed
$endgroup$
– rjm27trekkie
Nov 29 '18 at 15:44
add a comment |
$begingroup$
You mean $29-4$ instead of $29-5$ right? I think your proof works.
$endgroup$
– nafhgood
Nov 28 '18 at 13:47
$begingroup$
Yeah dunno how that got there. Fixed
$endgroup$
– rjm27trekkie
Nov 29 '18 at 15:44
$begingroup$
You mean $29-4$ instead of $29-5$ right? I think your proof works.
$endgroup$
– nafhgood
Nov 28 '18 at 13:47
$begingroup$
You mean $29-4$ instead of $29-5$ right? I think your proof works.
$endgroup$
– nafhgood
Nov 28 '18 at 13:47
$begingroup$
Yeah dunno how that got there. Fixed
$endgroup$
– rjm27trekkie
Nov 29 '18 at 15:44
$begingroup$
Yeah dunno how that got there. Fixed
$endgroup$
– rjm27trekkie
Nov 29 '18 at 15:44
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%2f3013116%2fprove-a-graph-g-has-crossing-number-crg-5%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
