Dtjytyk

Straight line with arrows and dots

Confusion with the nameplate of an induction motor

Touchscreen-controlled dentist office snowman collector game

Best approach to update all entries in a list that is paginated?

Force user to remove USB token

What is the dot in “1.2.4."

Good allowance savings plan?

Unreachable code, but reachable with exception

What happens with multiple copies of Humility and Glorious Anthem on the battlefield?

Is it ok to include an epilogue dedicated to colleagues who passed away in the end of the manuscript?

How can I discourage/prevent PCs from using door choke-points?

What is the blue range indicating on this manifold pressure gauge?

Rejected in 4th interview round citing insufficient years of experience

Playing ONE triplet (not three)

What to do when during a meeting client people start to fight (even physically) with each others?

Extension of Splitting Fields over An Arbitrary Field

Plywood subfloor won't screw down in a trailer home

Am I not good enough for you?

How to deal with a cynical class?

Is going from continuous data to categorical always wrong?

Does Linux have system calls to access all the features of the file systems it supports?

Is it illegal in Germany to take sick leave if you caused your own illness with food?

Is a lawful good "antagonist" effective?

When is a batch class instantiated when you schedule it?

Show that crossing number of Petersen graph must be >1?

Proving that crossing number for a graph is the lowest possiblePetersen graph is not a Cayley graphSimple crossing number questionRepresenting Petersen graph in root system $E_6$The Petersen graph is 3-connectedProve that the tesseract graph is non-planarUpper bound of number of edges of planar graph with k connected components and girth gNumber of faces in a planar graphHow many independent sets of size 4 has the Petersen graph?Prove a Graph $G$ Has Crossing number $Cr(G) = 5$

1

$begingroup$

Is there a way to show, that crossing number of Petersen graph must be > 1, without explicitly using Euler's formula (using girth, size and order of the graph)?

(Like, for example you can do with K_6 graph, when you show, that if K_6 would have 2 crossing and if one would remove the vertex common to both of the crossing, one would supposedly get a K_5 without crossing, which is a contradiction.)

( background: I showed that GP(5,2) can not be planar using Euler's formula, and found the representation of it with two crossing, now I just need to show, that there can not be only one crossing.)

discrete-mathematics graph-theory

share|cite|improve this question

asked Apr 3 '16 at 15:16

SaraSara

426

$endgroup$

add a comment | 

1

$begingroup$

Is there a way to show, that crossing number of Petersen graph must be > 1, without explicitly using Euler's formula (using girth, size and order of the graph)?

(Like, for example you can do with K_6 graph, when you show, that if K_6 would have 2 crossing and if one would remove the vertex common to both of the crossing, one would supposedly get a K_5 without crossing, which is a contradiction.)

( background: I showed that GP(5,2) can not be planar using Euler's formula, and found the representation of it with two crossing, now I just need to show, that there can not be only one crossing.)

discrete-mathematics graph-theory

share|cite|improve this question

asked Apr 3 '16 at 15:16

SaraSara

426

$endgroup$

add a comment | 

$begingroup$

Is there a way to show, that crossing number of Petersen graph must be > 1, without explicitly using Euler's formula (using girth, size and order of the graph)?

(Like, for example you can do with K_6 graph, when you show, that if K_6 would have 2 crossing and if one would remove the vertex common to both of the crossing, one would supposedly get a K_5 without crossing, which is a contradiction.)

( background: I showed that GP(5,2) can not be planar using Euler's formula, and found the representation of it with two crossing, now I just need to show, that there can not be only one crossing.)

discrete-mathematics graph-theory

share|cite|improve this question

asked Apr 3 '16 at 15:16

SaraSara

426

$endgroup$

share|cite|improve this question

asked Apr 3 '16 at 15:16

SaraSara

426

share|cite|improve this question

asked Apr 3 '16 at 15:16

SaraSara

426

asked Apr 3 '16 at 15:16

SaraSara

426

asked Apr 3 '16 at 15:16

SaraSara

426

2 Answers
2

active

oldest

votes

3

$begingroup$

Hint: Any cycle divides the plane into two sections, inside and outside. Given two disjoint cycles, $C,C'$, if one vertex of $C$ falls inside $C'$ and one falls outside $C'$ then you are guaranteed two crossings between the cycles.

You need to show that no matter how you move around points of the Peterson Graph in the plane, there are two cycles for which this property holds.

share|cite|improve this answer

edited Mar 9 at 22:20

answered Apr 3 '16 at 15:20

Stella BidermanStella Biderman

26.7k63375

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I am sorry, but I don't see exactly how this helps me? Can you be more specific, please?
  $endgroup$
  – Sara
  Apr 3 '16 at 16:13
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Sara Find two cycles within the Peterson graph that have the relation I described, and then you'll have proven what you want to show.
  $endgroup$
  – Stella Biderman
  Apr 3 '16 at 16:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I can find two cycles with the relation, but shouldn't then there be an argument that one is unable to find two disjoint cycles without this relation? (Or am I perhaps misinterpreting the term disjoint cycles (two cycles that do not share a common vertex))?
  $endgroup$
  – Sara
  Apr 3 '16 at 16:44
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Sara I don't know why you think that this relation necessarily would hold for every pair of cycles. It only need hold for two (and in fact there are non-intersecting cycles. That is the proper definition of "disjoint"
  $endgroup$
  – Stella Biderman
  Apr 3 '16 at 16:52
  
  
  

  
  
  
  

add a comment | 

1

$begingroup$

If you know the theorems of Kuratowski and Wagner: Assume the Petersen graph has crossing number 1, then construct a new graph from a drawing that verifies this fact by introducing a new vertex at the crossing.
Note that this graph has one crossing fewer than the original graph.
If you can show that this graph is not planar by finding a $K_5$ or $K_{3,3}$ Minor you showed that the crossing number is strictly larger than 1.

share|cite|improve this answer

answered Apr 20 '18 at 14:08

llmabellmabe

111

$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
});


}
});

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1726037%2fshow-that-crossing-number-of-petersen-graph-must-be-1%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

3

$begingroup$

Hint: Any cycle divides the plane into two sections, inside and outside. Given two disjoint cycles, $C,C'$, if one vertex of $C$ falls inside $C'$ and one falls outside $C'$ then you are guaranteed two crossings between the cycles.

You need to show that no matter how you move around points of the Peterson Graph in the plane, there are two cycles for which this property holds.

share|cite|improve this answer

edited Mar 9 at 22:20

answered Apr 3 '16 at 15:20

Stella BidermanStella Biderman

26.7k63375

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I am sorry, but I don't see exactly how this helps me? Can you be more specific, please?
  $endgroup$
  – Sara
  Apr 3 '16 at 16:13
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Sara Find two cycles within the Peterson graph that have the relation I described, and then you'll have proven what you want to show.
  $endgroup$
  – Stella Biderman
  Apr 3 '16 at 16:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I can find two cycles with the relation, but shouldn't then there be an argument that one is unable to find two disjoint cycles without this relation? (Or am I perhaps misinterpreting the term disjoint cycles (two cycles that do not share a common vertex))?
  $endgroup$
  – Sara
  Apr 3 '16 at 16:44
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Sara I don't know why you think that this relation necessarily would hold for every pair of cycles. It only need hold for two (and in fact there are non-intersecting cycles. That is the proper definition of "disjoint"
  $endgroup$
  – Stella Biderman
  Apr 3 '16 at 16:52
  
  
  

  
  
  
  

add a comment | 

3

$begingroup$

Hint: Any cycle divides the plane into two sections, inside and outside. Given two disjoint cycles, $C,C'$, if one vertex of $C$ falls inside $C'$ and one falls outside $C'$ then you are guaranteed two crossings between the cycles.

You need to show that no matter how you move around points of the Peterson Graph in the plane, there are two cycles for which this property holds.

share|cite|improve this answer

edited Mar 9 at 22:20

answered Apr 3 '16 at 15:20

Stella BidermanStella Biderman

26.7k63375

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I am sorry, but I don't see exactly how this helps me? Can you be more specific, please?
  $endgroup$
  – Sara
  Apr 3 '16 at 16:13
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Sara Find two cycles within the Peterson graph that have the relation I described, and then you'll have proven what you want to show.
  $endgroup$
  – Stella Biderman
  Apr 3 '16 at 16:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I can find two cycles with the relation, but shouldn't then there be an argument that one is unable to find two disjoint cycles without this relation? (Or am I perhaps misinterpreting the term disjoint cycles (two cycles that do not share a common vertex))?
  $endgroup$
  – Sara
  Apr 3 '16 at 16:44
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Sara I don't know why you think that this relation necessarily would hold for every pair of cycles. It only need hold for two (and in fact there are non-intersecting cycles. That is the proper definition of "disjoint"
  $endgroup$
  – Stella Biderman
  Apr 3 '16 at 16:52
  
  
  

  
  
  
  

add a comment | 

$begingroup$

Hint: Any cycle divides the plane into two sections, inside and outside. Given two disjoint cycles, $C,C'$, if one vertex of $C$ falls inside $C'$ and one falls outside $C'$ then you are guaranteed two crossings between the cycles.

You need to show that no matter how you move around points of the Peterson Graph in the plane, there are two cycles for which this property holds.

share|cite|improve this answer

edited Mar 9 at 22:20

answered Apr 3 '16 at 15:20

Stella BidermanStella Biderman

26.7k63375

$endgroup$

share|cite|improve this answer

edited Mar 9 at 22:20

answered Apr 3 '16 at 15:20

Stella BidermanStella Biderman

26.7k63375

answered Apr 3 '16 at 15:20

Stella BidermanStella Biderman

26.7k63375

answered Apr 3 '16 at 15:20

Stella BidermanStella Biderman

26.7k63375

1

$begingroup$

If you know the theorems of Kuratowski and Wagner: Assume the Petersen graph has crossing number 1, then construct a new graph from a drawing that verifies this fact by introducing a new vertex at the crossing.
Note that this graph has one crossing fewer than the original graph.
If you can show that this graph is not planar by finding a $K_5$ or $K_{3,3}$ Minor you showed that the crossing number is strictly larger than 1.

share|cite|improve this answer

answered Apr 20 '18 at 14:08

llmabellmabe

111

$endgroup$

add a comment | 

1

$begingroup$

If you know the theorems of Kuratowski and Wagner: Assume the Petersen graph has crossing number 1, then construct a new graph from a drawing that verifies this fact by introducing a new vertex at the crossing.
Note that this graph has one crossing fewer than the original graph.
If you can show that this graph is not planar by finding a $K_5$ or $K_{3,3}$ Minor you showed that the crossing number is strictly larger than 1.

share|cite|improve this answer

answered Apr 20 '18 at 14:08

llmabellmabe

111

$endgroup$

add a comment | 

$begingroup$

If you know the theorems of Kuratowski and Wagner: Assume the Petersen graph has crossing number 1, then construct a new graph from a drawing that verifies this fact by introducing a new vertex at the crossing.
Note that this graph has one crossing fewer than the original graph.
If you can show that this graph is not planar by finding a $K_5$ or $K_{3,3}$ Minor you showed that the crossing number is strictly larger than 1.

share|cite|improve this answer

answered Apr 20 '18 at 14:08

llmabellmabe

111

$endgroup$

share|cite|improve this answer

answered Apr 20 '18 at 14:08

llmabellmabe

111

answered Apr 20 '18 at 14:08

llmabellmabe

111

answered Apr 20 '18 at 14:08

llmabellmabe

111