Kuratowski's theorem in every case?

Clash Royale CLAN TAG#URR8PPP

up vote
3
down vote

favorite

1

I have the following graph $G$ (from Chartrand and Zhang, page 235, figure 9.9)

which is based on a maximal planar graph on 7 vertices with an additional edge (labeled $uv$). This graph is nonplanar because $m>3n-6$. Also, this graph does not contain either $K_3,3$ or $K_5$ as a subgraph (this is proved in the text). My question is why doesn't this contradict Kuratowski's theorem? Shouldn't there be a subdivision of one of these contained in $G$? But there are no vertices of degree two in this graph, so I'm not sure what subgraph I can take to build either of the critical graphs. I know the subgraph needs the edge $uv$, but that's all I know.

At this point in the text, contractions haven't been discussed, and subdivisions were just introduced, so I'm not sure how to proceed.

graph-theory planar-graph

share|cite|improve this question

asked Jul 21 at 17:17

Joshua Sasmor

284

add a comment | 

up vote
3
down vote

favorite

1

I have the following graph $G$ (from Chartrand and Zhang, page 235, figure 9.9)

which is based on a maximal planar graph on 7 vertices with an additional edge (labeled $uv$). This graph is nonplanar because $m>3n-6$. Also, this graph does not contain either $K_3,3$ or $K_5$ as a subgraph (this is proved in the text). My question is why doesn't this contradict Kuratowski's theorem? Shouldn't there be a subdivision of one of these contained in $G$? But there are no vertices of degree two in this graph, so I'm not sure what subgraph I can take to build either of the critical graphs. I know the subgraph needs the edge $uv$, but that's all I know.

At this point in the text, contractions haven't been discussed, and subdivisions were just introduced, so I'm not sure how to proceed.

graph-theory planar-graph

share|cite|improve this question

asked Jul 21 at 17:17

Joshua Sasmor

284

add a comment | 

up vote
3
down vote

favorite

1

up vote
3
down vote

favorite

1

1

I have the following graph $G$ (from Chartrand and Zhang, page 235, figure 9.9)

which is based on a maximal planar graph on 7 vertices with an additional edge (labeled $uv$). This graph is nonplanar because $m>3n-6$. Also, this graph does not contain either $K_3,3$ or $K_5$ as a subgraph (this is proved in the text). My question is why doesn't this contradict Kuratowski's theorem? Shouldn't there be a subdivision of one of these contained in $G$? But there are no vertices of degree two in this graph, so I'm not sure what subgraph I can take to build either of the critical graphs. I know the subgraph needs the edge $uv$, but that's all I know.

At this point in the text, contractions haven't been discussed, and subdivisions were just introduced, so I'm not sure how to proceed.

graph-theory planar-graph

share|cite|improve this question

asked Jul 21 at 17:17

Joshua Sasmor

284

I have the following graph $G$ (from Chartrand and Zhang, page 235, figure 9.9)

which is based on a maximal planar graph on 7 vertices with an additional edge (labeled $uv$). This graph is nonplanar because $m>3n-6$. Also, this graph does not contain either $K_3,3$ or $K_5$ as a subgraph (this is proved in the text). My question is why doesn't this contradict Kuratowski's theorem? Shouldn't there be a subdivision of one of these contained in $G$? But there are no vertices of degree two in this graph, so I'm not sure what subgraph I can take to build either of the critical graphs. I know the subgraph needs the edge $uv$, but that's all I know.

At this point in the text, contractions haven't been discussed, and subdivisions were just introduced, so I'm not sure how to proceed.

graph-theory planar-graph

share|cite|improve this question

asked Jul 21 at 17:17

Joshua Sasmor

284

share|cite|improve this question

share|cite|improve this question

asked Jul 21 at 17:17

Joshua Sasmor

284

asked Jul 21 at 17:17

Joshua Sasmor

284

asked Jul 21 at 17:17

Joshua Sasmor

284

284

add a comment | 

add a comment | 

3 Answers
3

active

oldest

votes

up vote
5
down vote



accepted

There is a subdivided $K_3,3$ embedded in this graph. Each of $u,z,s$ are connected to each of $v,t,y$ by distinct edges of your graph, except that $u$ and $y$ are connected the two edge path $uxy$.

share|cite|improve this answer

answered Jul 21 at 17:32

Lee Mosher

45.6k33478

• 
  
  
  

  
  

  
  
  
  
  
  

  
  It took me about 45 minutes to follow the examples in the text, and now I think I understand the subgraph/subdivision distinction. I found this $K_3,3$ and then came back to find your answer - thank you!
  – Joshua Sasmor
  Jul 21 at 18:07
  

  
  
  
  

add a comment | 

up vote
5
down vote

$u,s,x,v,t$ forms a subdivision of $K_5$ in the graph. This can be formed by deleting the edges from $y$ and $z$ to $s$ and $t$, then smoothing out the path $xyzv$.

share|cite|improve this answer

answered Jul 21 at 17:23

Parcly Taxel

33.6k136588

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thank you - this was helpful - I found a $K_3,3$, but I wasn't sure about the $K_5$.
  – Joshua Sasmor
  Jul 21 at 18:07
  

  
  
  
  

add a comment | 

up vote
1
down vote

Check again the statement of Kuratowski's theorem. It does not talk about subgraphs, but some kind of graph minors. This example is a perfect illustration why Kuratowski's theorem SHOULD NOT talk about subgraphs.

share|cite|improve this answer

answered Jul 21 at 17:52

A. Pongrácz

2,263221

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thank you - it calls for a "subdivision of $K_3,3$ or $K_5$" I wasn't sure how to find that.
  – Joshua Sasmor
  Jul 21 at 18:06
  

  
  
  
  

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',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
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

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2858693%2fkuratowskis-theorem-in-every-case%23new-answer', 'question_page');

);

Post as a guest

Name Email

3 Answers
3

active

oldest

votes

3 Answers
3

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
5
down vote



accepted

There is a subdivided $K_3,3$ embedded in this graph. Each of $u,z,s$ are connected to each of $v,t,y$ by distinct edges of your graph, except that $u$ and $y$ are connected the two edge path $uxy$.

share|cite|improve this answer

answered Jul 21 at 17:32

Lee Mosher

45.6k33478

• 
  
  
  

  
  

  
  
  
  
  
  

  
  It took me about 45 minutes to follow the examples in the text, and now I think I understand the subgraph/subdivision distinction. I found this $K_3,3$ and then came back to find your answer - thank you!
  – Joshua Sasmor
  Jul 21 at 18:07
  

  
  
  
  

add a comment | 

up vote
5
down vote



accepted

There is a subdivided $K_3,3$ embedded in this graph. Each of $u,z,s$ are connected to each of $v,t,y$ by distinct edges of your graph, except that $u$ and $y$ are connected the two edge path $uxy$.

share|cite|improve this answer

answered Jul 21 at 17:32

Lee Mosher

45.6k33478

• 
  
  
  

  
  

  
  
  
  
  
  

  
  It took me about 45 minutes to follow the examples in the text, and now I think I understand the subgraph/subdivision distinction. I found this $K_3,3$ and then came back to find your answer - thank you!
  – Joshua Sasmor
  Jul 21 at 18:07
  

  
  
  
  

add a comment | 

up vote
5
down vote



accepted

up vote
5
down vote



accepted

There is a subdivided $K_3,3$ embedded in this graph. Each of $u,z,s$ are connected to each of $v,t,y$ by distinct edges of your graph, except that $u$ and $y$ are connected the two edge path $uxy$.

share|cite|improve this answer

answered Jul 21 at 17:32

Lee Mosher

45.6k33478

There is a subdivided $K_3,3$ embedded in this graph. Each of $u,z,s$ are connected to each of $v,t,y$ by distinct edges of your graph, except that $u$ and $y$ are connected the two edge path $uxy$.

share|cite|improve this answer

answered Jul 21 at 17:32

Lee Mosher

45.6k33478

share|cite|improve this answer

share|cite|improve this answer

answered Jul 21 at 17:32

Lee Mosher

45.6k33478

answered Jul 21 at 17:32

Lee Mosher

45.6k33478

answered Jul 21 at 17:32

Lee Mosher

45.6k33478

45.6k33478

• 
  
  
  

  
  

  
  
  
  
  
  

  
  It took me about 45 minutes to follow the examples in the text, and now I think I understand the subgraph/subdivision distinction. I found this $K_3,3$ and then came back to find your answer - thank you!
  – Joshua Sasmor
  Jul 21 at 18:07
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  It took me about 45 minutes to follow the examples in the text, and now I think I understand the subgraph/subdivision distinction. I found this $K_3,3$ and then came back to find your answer - thank you!
  – Joshua Sasmor
  Jul 21 at 18:07
  

  
  
  
  

It took me about 45 minutes to follow the examples in the text, and now I think I understand the subgraph/subdivision distinction. I found this $K_3,3$ and then came back to find your answer - thank you!
– Joshua Sasmor
Jul 21 at 18:07

It took me about 45 minutes to follow the examples in the text, and now I think I understand the subgraph/subdivision distinction. I found this $K_3,3$ and then came back to find your answer - thank you!
– Joshua Sasmor
Jul 21 at 18:07

add a comment | 

up vote
5
down vote

$u,s,x,v,t$ forms a subdivision of $K_5$ in the graph. This can be formed by deleting the edges from $y$ and $z$ to $s$ and $t$, then smoothing out the path $xyzv$.

share|cite|improve this answer

answered Jul 21 at 17:23

Parcly Taxel

33.6k136588

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thank you - this was helpful - I found a $K_3,3$, but I wasn't sure about the $K_5$.
  – Joshua Sasmor
  Jul 21 at 18:07
  

  
  
  
  

add a comment | 

up vote
5
down vote

$u,s,x,v,t$ forms a subdivision of $K_5$ in the graph. This can be formed by deleting the edges from $y$ and $z$ to $s$ and $t$, then smoothing out the path $xyzv$.

share|cite|improve this answer

answered Jul 21 at 17:23

Parcly Taxel

33.6k136588

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thank you - this was helpful - I found a $K_3,3$, but I wasn't sure about the $K_5$.
  – Joshua Sasmor
  Jul 21 at 18:07
  

  
  
  
  

add a comment | 

up vote
5
down vote

up vote
5
down vote

$u,s,x,v,t$ forms a subdivision of $K_5$ in the graph. This can be formed by deleting the edges from $y$ and $z$ to $s$ and $t$, then smoothing out the path $xyzv$.

share|cite|improve this answer

answered Jul 21 at 17:23

Parcly Taxel

33.6k136588

$u,s,x,v,t$ forms a subdivision of $K_5$ in the graph. This can be formed by deleting the edges from $y$ and $z$ to $s$ and $t$, then smoothing out the path $xyzv$.

share|cite|improve this answer

answered Jul 21 at 17:23

Parcly Taxel

33.6k136588

share|cite|improve this answer

share|cite|improve this answer

answered Jul 21 at 17:23

Parcly Taxel

33.6k136588

answered Jul 21 at 17:23

Parcly Taxel

33.6k136588

answered Jul 21 at 17:23

Parcly Taxel

33.6k136588

33.6k136588

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thank you - this was helpful - I found a $K_3,3$, but I wasn't sure about the $K_5$.
  – Joshua Sasmor
  Jul 21 at 18:07
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thank you - this was helpful - I found a $K_3,3$, but I wasn't sure about the $K_5$.
  – Joshua Sasmor
  Jul 21 at 18:07
  

  
  
  
  

Thank you - this was helpful - I found a $K_3,3$, but I wasn't sure about the $K_5$.
– Joshua Sasmor
Jul 21 at 18:07

Thank you - this was helpful - I found a $K_3,3$, but I wasn't sure about the $K_5$.
– Joshua Sasmor
Jul 21 at 18:07

add a comment | 

up vote
1
down vote

Check again the statement of Kuratowski's theorem. It does not talk about subgraphs, but some kind of graph minors. This example is a perfect illustration why Kuratowski's theorem SHOULD NOT talk about subgraphs.

share|cite|improve this answer

answered Jul 21 at 17:52

A. Pongrácz

2,263221

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thank you - it calls for a "subdivision of $K_3,3$ or $K_5$" I wasn't sure how to find that.
  – Joshua Sasmor
  Jul 21 at 18:06
  

  
  
  
  

add a comment | 

up vote
1
down vote

Check again the statement of Kuratowski's theorem. It does not talk about subgraphs, but some kind of graph minors. This example is a perfect illustration why Kuratowski's theorem SHOULD NOT talk about subgraphs.

share|cite|improve this answer

answered Jul 21 at 17:52

A. Pongrácz

2,263221

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thank you - it calls for a "subdivision of $K_3,3$ or $K_5$" I wasn't sure how to find that.
  – Joshua Sasmor
  Jul 21 at 18:06
  

  
  
  
  

add a comment | 

up vote
1
down vote

up vote
1
down vote

Check again the statement of Kuratowski's theorem. It does not talk about subgraphs, but some kind of graph minors. This example is a perfect illustration why Kuratowski's theorem SHOULD NOT talk about subgraphs.

share|cite|improve this answer

answered Jul 21 at 17:52

A. Pongrácz

2,263221

Check again the statement of Kuratowski's theorem. It does not talk about subgraphs, but some kind of graph minors. This example is a perfect illustration why Kuratowski's theorem SHOULD NOT talk about subgraphs.

share|cite|improve this answer

answered Jul 21 at 17:52

A. Pongrácz

2,263221

share|cite|improve this answer

share|cite|improve this answer

answered Jul 21 at 17:52

A. Pongrácz

2,263221

answered Jul 21 at 17:52

A. Pongrácz

2,263221

answered Jul 21 at 17:52

A. Pongrácz

2,263221

2,263221

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thank you - it calls for a "subdivision of $K_3,3$ or $K_5$" I wasn't sure how to find that.
  – Joshua Sasmor
  Jul 21 at 18:06
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Thank you - it calls for a "subdivision of $K_3,3$ or $K_5$" I wasn't sure how to find that.
  – Joshua Sasmor
  Jul 21 at 18:06
  

  
  
  
  

Thank you - it calls for a "subdivision of $K_3,3$ or $K_5$" I wasn't sure how to find that.
– Joshua Sasmor
Jul 21 at 18:06

Thank you - it calls for a "subdivision of $K_3,3$ or $K_5$" I wasn't sure how to find that.
– Joshua Sasmor
Jul 21 at 18:06

add a comment | 

 

draft saved

draft discarded

 

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

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2858693%2fkuratowskis-theorem-in-every-case%23new-answer', 'question_page');

);

Post as a guest

Name Email

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

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

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

Name Email

Name Email

Name

Email

Name Email

Name

Email