Timeline for Why $K_5$ and $K_{3,3}$?
Current License: CC BY-SA 4.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 27, 2023 at 18:38 | answer | added | rimu | timeline score: 8 | |
| Mar 10, 2021 at 3:04 | review | Close votes | |||
| Mar 10, 2021 at 17:25 | |||||
| Mar 8, 2021 at 21:06 | comment | added | lambda | @rimu I was responding to this bit of your post: "Of course, $K_5$ is the smallest non-planar graph at all, but then, which role plays $K_{3,3}$ in the theorem?" I agree however that the observation that both graphs can be considered the "smallest" doesn't really explain anything. | |
| Mar 8, 2021 at 18:45 | comment | added | rimu | @SamHopkins 4 is the minimal number of edges that the faces of the non-planar graph $K_{3,3}$ would have if it had a planar embedding. I hope this makes it clearer... | |
| Mar 8, 2021 at 18:42 | comment | added | rimu | @lambda This is an interesting observation. If someone could write a proof of Kuratowski's theorem based on this fact, I would count it as "explanation" of $K_5$ and $K_{3,3}$. But I don't think it is easy. | |
| Mar 8, 2021 at 2:25 | comment | added | Sam Hopkins | @domotorp: in what sense does $K_{3,3}$ have faces? It is non-planar... | |
| Mar 6, 2021 at 19:31 | comment | added | domotorp | I think that rather than the number of edges, what's important about $K_{3,3}$ is that it is the smallest graph with all faces being of size at least 4. | |
| Mar 5, 2021 at 14:28 | comment | added | lambda | $K_{3,3}$ is the smallest nonplanar graph if you're counting by the number of edges. | |
| Mar 5, 2021 at 8:06 | history | edited | Martin Sleziak | CC BY-SA 4.0 |
edited tags
|
| Mar 5, 2021 at 2:40 | review | Close votes | |||
| Mar 5, 2021 at 12:51 | |||||
| Mar 5, 2021 at 2:26 | comment | added | Will Jagy | @LSpice. Not really. It appears the person asking has no knowledge of the area. The book can repair that. | |
| Mar 5, 2021 at 2:23 | comment | added | LSpice | @WillJagy, presumably the book (Gross and Tucker - Topological graph theory) you reference proves the planarity theorem, but did you mean to link to anything more specific in the book? | |
| Mar 4, 2021 at 21:16 | comment | added | Will Jagy | google.com/books/edition/Topological_Graph_Theory/… | |
| Mar 4, 2021 at 20:58 | comment | added | Steven Stadnicki | Once you recognize that the property of planarity is closed under graph minors, the Robertson-Seymour therorem guarantees you that there's some finite set of graphs such that any non-planar graph must contain (a subdivision of) one of them. | |
| Mar 4, 2021 at 20:28 | comment | added | Fedor Petrov | They are minor-minimal non-planar graph (any proper minor of any of them is planar). Any other non-planar graph is not minor-minimal, since it contains $K_5$ or $K_{33}$ as a minor. | |
| Mar 4, 2021 at 20:17 | review | First posts | |||
| Mar 4, 2021 at 20:20 | |||||
| Mar 4, 2021 at 20:12 | history | asked | rimu | CC BY-SA 4.0 |