Planar graph or not (Kuratowski's Theorem)
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
So the question is whether the graph given is planar or not. After some trial and error I think it is NOT planar, so I want to prove it using Kuratowski's Theorem but I couldn't break it down to $K_5$ or $K_3,3$. Would appreciate any help on this!
Also in general, is there any strategy that we can use when trying to apply Kuratowski's Theorem? Or any thing that can help to determine whether we should aim for $K_5$ or $K_3,3$? Or is it just purely trial and error? I got so frustrated when I could not figure it out.
discrete-mathematics graph-theory planar-graph
add a comment |Â
up vote
1
down vote
favorite
So the question is whether the graph given is planar or not. After some trial and error I think it is NOT planar, so I want to prove it using Kuratowski's Theorem but I couldn't break it down to $K_5$ or $K_3,3$. Would appreciate any help on this!
Also in general, is there any strategy that we can use when trying to apply Kuratowski's Theorem? Or any thing that can help to determine whether we should aim for $K_5$ or $K_3,3$? Or is it just purely trial and error? I got so frustrated when I could not figure it out.
discrete-mathematics graph-theory planar-graph
What version of Kuratowski do you use: the one with minors? or subgraphs by subdivisions?
â Henno Brandsma
3 hours ago
3
There aren't too many points of degree 4, so I'd say go for $K_3,3$,
â Henno Brandsma
3 hours ago
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
So the question is whether the graph given is planar or not. After some trial and error I think it is NOT planar, so I want to prove it using Kuratowski's Theorem but I couldn't break it down to $K_5$ or $K_3,3$. Would appreciate any help on this!
Also in general, is there any strategy that we can use when trying to apply Kuratowski's Theorem? Or any thing that can help to determine whether we should aim for $K_5$ or $K_3,3$? Or is it just purely trial and error? I got so frustrated when I could not figure it out.
discrete-mathematics graph-theory planar-graph
So the question is whether the graph given is planar or not. After some trial and error I think it is NOT planar, so I want to prove it using Kuratowski's Theorem but I couldn't break it down to $K_5$ or $K_3,3$. Would appreciate any help on this!
Also in general, is there any strategy that we can use when trying to apply Kuratowski's Theorem? Or any thing that can help to determine whether we should aim for $K_5$ or $K_3,3$? Or is it just purely trial and error? I got so frustrated when I could not figure it out.
discrete-mathematics graph-theory planar-graph
discrete-mathematics graph-theory planar-graph
asked 3 hours ago
M. W
375
375
What version of Kuratowski do you use: the one with minors? or subgraphs by subdivisions?
â Henno Brandsma
3 hours ago
3
There aren't too many points of degree 4, so I'd say go for $K_3,3$,
â Henno Brandsma
3 hours ago
add a comment |Â
What version of Kuratowski do you use: the one with minors? or subgraphs by subdivisions?
â Henno Brandsma
3 hours ago
3
There aren't too many points of degree 4, so I'd say go for $K_3,3$,
â Henno Brandsma
3 hours ago
What version of Kuratowski do you use: the one with minors? or subgraphs by subdivisions?
â Henno Brandsma
3 hours ago
What version of Kuratowski do you use: the one with minors? or subgraphs by subdivisions?
â Henno Brandsma
3 hours ago
3
3
There aren't too many points of degree 4, so I'd say go for $K_3,3$,
â Henno Brandsma
3 hours ago
There aren't too many points of degree 4, so I'd say go for $K_3,3$,
â Henno Brandsma
3 hours ago
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
5
down vote
accepted
Remove the edge $BD$ and suppress vertices $B,D$. The original graph thus contains a subdivision of this resulting graph, which is isomorphic to $K_3,3$, so the original graph is not planar.
Thanks for your answer!
â M. W
26 mins ago
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
accepted
Remove the edge $BD$ and suppress vertices $B,D$. The original graph thus contains a subdivision of this resulting graph, which is isomorphic to $K_3,3$, so the original graph is not planar.
Thanks for your answer!
â M. W
26 mins ago
add a comment |Â
up vote
5
down vote
accepted
Remove the edge $BD$ and suppress vertices $B,D$. The original graph thus contains a subdivision of this resulting graph, which is isomorphic to $K_3,3$, so the original graph is not planar.
Thanks for your answer!
â M. W
26 mins ago
add a comment |Â
up vote
5
down vote
accepted
up vote
5
down vote
accepted
Remove the edge $BD$ and suppress vertices $B,D$. The original graph thus contains a subdivision of this resulting graph, which is isomorphic to $K_3,3$, so the original graph is not planar.
Remove the edge $BD$ and suppress vertices $B,D$. The original graph thus contains a subdivision of this resulting graph, which is isomorphic to $K_3,3$, so the original graph is not planar.
answered 3 hours ago
Parcly Taxel
37.6k137096
37.6k137096
Thanks for your answer!
â M. W
26 mins ago
add a comment |Â
Thanks for your answer!
â M. W
26 mins ago
Thanks for your answer!
â M. W
26 mins ago
Thanks for your answer!
â M. W
26 mins ago
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2973019%2fplanar-graph-or-not-kuratowskis-theorem%23new-answer', 'question_page');
);
Post as a guest
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
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
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
What version of Kuratowski do you use: the one with minors? or subgraphs by subdivisions?
â Henno Brandsma
3 hours ago
3
There aren't too many points of degree 4, so I'd say go for $K_3,3$,
â Henno Brandsma
3 hours ago