Prove that the thickness of $K_6$ is $2$. (That is, find two graphs $G$ and $H$ such that $G∪H = K_6$ and...
$begingroup$
Prove that the thickness of $K_6$ is $2$. (That is, find two graphs $G$ and $H$ such that $Gcup H =K_6$
and $G$ and $H$ are both planar.)
graph-theory planar-graph
edited Dec 14 '18 at 4:33
Carl Schildkraut
11.9k11444
asked Dec 14 '18 at 3:32
Neomy GutierrezNeomy Gutierrez
21
$endgroup$
closed as off-topic by T. Bongers, Lord Shark the Unknown, BigbearZzz, Martin R, platty Dec 14 '18 at 8:15
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – T. Bongers, Lord Shark the Unknown, Martin R, platty
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
Prove that the thickness of $K_6$ is $2$. (That is, find two graphs $G$ and $H$ such that $Gcup H =K_6$
and $G$ and $H$ are both planar.)
graph-theory planar-graph
edited Dec 14 '18 at 4:33
Carl Schildkraut
11.9k11444
asked Dec 14 '18 at 3:32
Neomy GutierrezNeomy Gutierrez
21
$endgroup$
closed as off-topic by T. Bongers, Lord Shark the Unknown, BigbearZzz, Martin R, platty Dec 14 '18 at 8:15
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – T. Bongers, Lord Shark the Unknown, Martin R, platty
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
Prove that the thickness of $K_6$ is $2$. (That is, find two graphs $G$ and $H$ such that $Gcup H =K_6$
and $G$ and $H$ are both planar.)
graph-theory planar-graph
edited Dec 14 '18 at 4:33
Carl Schildkraut
11.9k11444
asked Dec 14 '18 at 3:32
Neomy GutierrezNeomy Gutierrez
21
$endgroup$
Prove that the thickness of $K_6$ is $2$. (That is, find two graphs $G$ and $H$ such that $Gcup H =K_6$
and $G$ and $H$ are both planar.)
graph-theory planar-graph
graph-theory planar-graph
edited Dec 14 '18 at 4:33
Carl Schildkraut
11.9k11444
asked Dec 14 '18 at 3:32
Neomy GutierrezNeomy Gutierrez
21
edited Dec 14 '18 at 4:33
Carl Schildkraut
11.9k11444
asked Dec 14 '18 at 3:32
Neomy GutierrezNeomy Gutierrez
21
edited Dec 14 '18 at 4:33
Carl Schildkraut
11.9k11444
edited Dec 14 '18 at 4:33
Carl Schildkraut
11.9k11444
edited Dec 14 '18 at 4:33
Carl Schildkraut
11.9k11444
11.9k11444
asked Dec 14 '18 at 3:32
Neomy GutierrezNeomy Gutierrez
21
asked Dec 14 '18 at 3:32
Neomy GutierrezNeomy Gutierrez
21
asked Dec 14 '18 at 3:32
Neomy GutierrezNeomy Gutierrez
21
21
closed as off-topic by T. Bongers, Lord Shark the Unknown, BigbearZzz, Martin R, platty Dec 14 '18 at 8:15
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – T. Bongers, Lord Shark the Unknown, Martin R, platty
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by T. Bongers, Lord Shark the Unknown, BigbearZzz, Martin R, platty Dec 14 '18 at 8:15
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – T. Bongers, Lord Shark the Unknown, Martin R, platty
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Consider $G=K_4$ and $H=K_2$ connected too all vertices of complement of $K_4$?
answered Dec 14 '18 at 3:41
mathpadawanmathpadawan
1,903422
$endgroup$
1
$begingroup$
A more planar drawing of $H$ looks like <<|>>.
$endgroup$
– Alex Ravsky
Dec 14 '18 at 3:45
add a comment |
$begingroup$
Let $G$ be a $K_5$ without an edge. Then $H$ is a $K_3$ with three leafs attached to one of its vertices.
answered Dec 14 '18 at 3:41
Alex RavskyAlex Ravsky
42.9k32483
$endgroup$
add a comment |
$begingroup$
I wonder how you tried to solve this problem. Me not being very clever, I decided to just draw the biggest planar subgraph of $K_6$ that I could, and hope that the complement would be planar. This must be my lucky day, because I succeeded on my first try. I put down $6$ points and started joining them with edges as long as I could without crossing. I ended up with $12$ edges: first I drew a hexagon, then a triangle inscribed in the hexagon, then $3$ more edges outside the hexagon. The complementary graph had only $3$ edges, so of course it was planar.
P.S. Here's a short description of the two graphs I ended up with: one of them is a $1$-regular graph on $6$ vertices, the other is a $4$-regular graph on $6$ vertices.
answered Dec 14 '18 at 6:51
bofbof
52.6k559121
$endgroup$
add a comment |
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Consider $G=K_4$ and $H=K_2$ connected too all vertices of complement of $K_4$?
answered Dec 14 '18 at 3:41
mathpadawanmathpadawan
1,903422
$endgroup$
1
$begingroup$
A more planar drawing of $H$ looks like <<|>>.
$endgroup$
– Alex Ravsky
Dec 14 '18 at 3:45
add a comment |
$begingroup$
Consider $G=K_4$ and $H=K_2$ connected too all vertices of complement of $K_4$?
answered Dec 14 '18 at 3:41
mathpadawanmathpadawan
1,903422
$endgroup$
1
$begingroup$
A more planar drawing of $H$ looks like <<|>>.
$endgroup$
– Alex Ravsky
Dec 14 '18 at 3:45
add a comment |
$begingroup$
Consider $G=K_4$ and $H=K_2$ connected too all vertices of complement of $K_4$?
answered Dec 14 '18 at 3:41
mathpadawanmathpadawan
1,903422
$endgroup$
Consider $G=K_4$ and $H=K_2$ connected too all vertices of complement of $K_4$?
answered Dec 14 '18 at 3:41
mathpadawanmathpadawan
1,903422
answered Dec 14 '18 at 3:41
mathpadawanmathpadawan
1,903422
answered Dec 14 '18 at 3:41
mathpadawanmathpadawan
1,903422
answered Dec 14 '18 at 3:41
mathpadawanmathpadawan
1,903422
1,903422
1
$begingroup$
A more planar drawing of $H$ looks like <<|>>.
$endgroup$
– Alex Ravsky
Dec 14 '18 at 3:45
add a comment |
1
$begingroup$
A more planar drawing of $H$ looks like <<|>>.
$endgroup$
– Alex Ravsky
Dec 14 '18 at 3:45
1
1
$begingroup$
A more planar drawing of $H$ looks like <<|>>.
$endgroup$
– Alex Ravsky
Dec 14 '18 at 3:45
$begingroup$
A more planar drawing of $H$ looks like <<|>>.
$endgroup$
– Alex Ravsky
Dec 14 '18 at 3:45
add a comment |
$begingroup$
Let $G$ be a $K_5$ without an edge. Then $H$ is a $K_3$ with three leafs attached to one of its vertices.
answered Dec 14 '18 at 3:41
Alex RavskyAlex Ravsky
42.9k32483
$endgroup$
add a comment |
$begingroup$
Let $G$ be a $K_5$ without an edge. Then $H$ is a $K_3$ with three leafs attached to one of its vertices.
answered Dec 14 '18 at 3:41
Alex RavskyAlex Ravsky
42.9k32483
$endgroup$
add a comment |
$begingroup$
Let $G$ be a $K_5$ without an edge. Then $H$ is a $K_3$ with three leafs attached to one of its vertices.
answered Dec 14 '18 at 3:41
Alex RavskyAlex Ravsky
42.9k32483
$endgroup$
Let $G$ be a $K_5$ without an edge. Then $H$ is a $K_3$ with three leafs attached to one of its vertices.
answered Dec 14 '18 at 3:41
Alex RavskyAlex Ravsky
42.9k32483
answered Dec 14 '18 at 3:41
Alex RavskyAlex Ravsky
42.9k32483
answered Dec 14 '18 at 3:41
Alex RavskyAlex Ravsky
42.9k32483
answered Dec 14 '18 at 3:41
Alex RavskyAlex Ravsky
42.9k32483
42.9k32483
add a comment |
add a comment |
$begingroup$
I wonder how you tried to solve this problem. Me not being very clever, I decided to just draw the biggest planar subgraph of $K_6$ that I could, and hope that the complement would be planar. This must be my lucky day, because I succeeded on my first try. I put down $6$ points and started joining them with edges as long as I could without crossing. I ended up with $12$ edges: first I drew a hexagon, then a triangle inscribed in the hexagon, then $3$ more edges outside the hexagon. The complementary graph had only $3$ edges, so of course it was planar.
P.S. Here's a short description of the two graphs I ended up with: one of them is a $1$-regular graph on $6$ vertices, the other is a $4$-regular graph on $6$ vertices.
answered Dec 14 '18 at 6:51
bofbof
52.6k559121
$endgroup$
add a comment |
$begingroup$
I wonder how you tried to solve this problem. Me not being very clever, I decided to just draw the biggest planar subgraph of $K_6$ that I could, and hope that the complement would be planar. This must be my lucky day, because I succeeded on my first try. I put down $6$ points and started joining them with edges as long as I could without crossing. I ended up with $12$ edges: first I drew a hexagon, then a triangle inscribed in the hexagon, then $3$ more edges outside the hexagon. The complementary graph had only $3$ edges, so of course it was planar.
P.S. Here's a short description of the two graphs I ended up with: one of them is a $1$-regular graph on $6$ vertices, the other is a $4$-regular graph on $6$ vertices.
answered Dec 14 '18 at 6:51
bofbof
52.6k559121
$endgroup$
add a comment |
$begingroup$
I wonder how you tried to solve this problem. Me not being very clever, I decided to just draw the biggest planar subgraph of $K_6$ that I could, and hope that the complement would be planar. This must be my lucky day, because I succeeded on my first try. I put down $6$ points and started joining them with edges as long as I could without crossing. I ended up with $12$ edges: first I drew a hexagon, then a triangle inscribed in the hexagon, then $3$ more edges outside the hexagon. The complementary graph had only $3$ edges, so of course it was planar.
P.S. Here's a short description of the two graphs I ended up with: one of them is a $1$-regular graph on $6$ vertices, the other is a $4$-regular graph on $6$ vertices.
answered Dec 14 '18 at 6:51
bofbof
52.6k559121
$endgroup$
I wonder how you tried to solve this problem. Me not being very clever, I decided to just draw the biggest planar subgraph of $K_6$ that I could, and hope that the complement would be planar. This must be my lucky day, because I succeeded on my first try. I put down $6$ points and started joining them with edges as long as I could without crossing. I ended up with $12$ edges: first I drew a hexagon, then a triangle inscribed in the hexagon, then $3$ more edges outside the hexagon. The complementary graph had only $3$ edges, so of course it was planar.
P.S. Here's a short description of the two graphs I ended up with: one of them is a $1$-regular graph on $6$ vertices, the other is a $4$-regular graph on $6$ vertices.
answered Dec 14 '18 at 6:51
bofbof
52.6k559121
edited Dec 14 '18 at 6:56
answered Dec 14 '18 at 6:51
bofbof
52.6k559121
answered Dec 14 '18 at 6:51
bofbof
52.6k559121
answered Dec 14 '18 at 6:51
bofbof
52.6k559121
52.6k559121
add a comment |
add a comment |
