Toroidal Complete Graphs
In the graphs above, only K 4 can be drawn on a plane without any edge crossings, as illustrated below:
This cannot be done with K 5 , yet it can be drawn on a torus without any edge crossings:
Top view of the torus. The blue dotted line is on the bottom side.
Can K 6 and K 7 be drawn on a torus without edge crossings?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
5 solutions
For now I cannot find a proof that K 8 is toroidal.
Proof that K 5 is not planar:
Lemma: A complete planar graph must be a triangulation. Otherwise, there exists a face with more than 3 edges, hence implying that the graph is not complete as additional edges can be drawn to connect the vertices of the face.
K 5 has ( 2 5 ) = 1 0 edges. If K 5 is planar, K 5 must be a triangulation by the lemma. Furthermore, each edge on a planar graph is shared between 2 faces. This means every edge on a K 5 graph is the edge of 2 triangles (faces of K 5 ). This means if K 5 is planar, it must have 1 0 × 3 2 faces, which is not an integer. Hence contradiction.
This can be extended to prove that K n n > 4 are not planar since they contain K 5 .
Log in to reply
For K 8 I believe that a combination of Euler's formula and handshaking lemma should work to produce a contradiction on the number of faces.
Log in to reply
For K8, it's easy to prove using the generalisation of the four color theorem generalisation, stating that every graph drawn on a torus can be colored with 7 colors or less. Since K8 needs 8 colors, it can't be drawn on a torus.
Log in to reply
@Antoine Labelle – Well that's correct but I'm uncertain if the proof of the toroidal 7 color theorem would ultimately rely on the fact that K8 is non-toroidal, which invokes circular argument.
Since a planar map can be 4-colored, you can make K4 a planar graph. Just create a 4 region map that requires 4 colors, shrink the regions to points and the borders to connections,
If you could make a 5 region map that requires 5 colors, then K5 would be planar.
Since the equivalent to the four color theorem on the plane is the seven color theorem on the torus, you can draw all up to K7 on the torus.
Can you check your equivalence chain?
IE You have to prove that "there exists a 7 region map that requires 7 colors on the torus", in order to conclude that "by the seven color theorem, we can draw a K7 on the torus". The existence of such a map isn't guaranteed by the theorem, since the example (showing that at least 7 colors are needed) could require many regions.
Log in to reply
Take a seven coloring of a torus. It has seven regions and each borders the other six. Pick a point (vertex) in each region and connect each with a line (edge) through the border. So you can draw K7 with no crossing edges.
It's too hard to draw, but here's the K4 analog.
Log in to reply
To clarify:
Take a seven coloring of a torus. It has seven regions and each borders the other six.
This is the assumption that you're making, namely that any seven coloring of the torus consists of seven regions that each borders the other six. In the event that the seven coloring of the torus requires (say) 20 regions to force out the 7th color, then the conclusion no longer follows.
Note: For this version of the writeup, you are not using the full force of the seven color torus.
To be explicit, the idea in your solution is:
There exists a way (as shown in the comment) to cut the plane into 4 regions, each of which borders the other 3. Hence, we can put a K 4 on the plane by taking the dual graph.
Similarly, there exists a way (ideally, show it) to cut the torus into 7 regions, each of which borders the other six. Hence, we can put a K 7 on the torus by taking the dual graph.
In particular, this approach does not require the 4-color / 7-color theorem. Yes, the existance of the 4/7 region map shows that "at least 4/7 colors are needed to color the plane/torus".
Please someone correct me if my reasoning is incorrect here. I started with the fact that the Euler characteristic for a torus is zero, i.e., V − E + F = 0 . Then if K 7 can be drawn on a torus with no edge crossings, then it can be done with K 6 because K 6 is a subgraph of K 7 . For K 7 , V = 7 and E = 7 ⋅ 6 / 2 = 2 1 . Next, since K 7 is complete, no face has four or greater enclosing edges. If there were such a face, then there would be a diagonal that is not connected, contradicting the fact that K 7 is complete (it is not entirely clear to me that this is true on a torus, but it seems like a reasonable assumption). Next, if all the faces are triangular, then F = 3 2 E = 1 4 . We see then that V − E + F = 7 − 2 1 + 1 4 = 0 , which means both graphs can be drawn on a torus without any crossings.
http://mathworld.wolfram.com/GraphGenus.html γ ( K 7 ) = ⌈ 1 2 ( 7 − 3 ) ( 7 − 4 ) ⌉ = 1
I instead solve this another way without doing complicated math, but instead follow the teachings of another course, logic. now the answers given are k6 is correct, both correct, or neither correct. now with the information given we can solve without solving. the answers both are incorrect/correct are easily given to have a fifty fifty, but k6 is a tricky answer. why only allow k6 to be a answer, but not just k7? because it was used to trick you into thinking it is the only correct answer, and so when you solve that k6 can be solved you believe that k7 cannotand so might not even try k7, but upon solving that k6 is solvable, then you candeduce that neither is correct is not the correct answer, and so the only plausible answer would be both are correct. also if math class taught me anything is that cool math stuff like this can happen. there you go I just solved it without knowing a thing of what was being taught.
You haven't attempted enough Brilliant problems to know that you can't simply eliminate options for such silly reasons. In, many problems with 2 choices have significantly less than 50% people getting it right showing that these problems are tricky and that guessing is, in fact, a better strategy than applying flawed logic.
Log in to reply
Why are you taking what I have done on this website to base my knowledge? I have lived and experienced many things longer than I have been on brilliant so obviously that is a silly reason to why my way of eliminating options, and they aren't silly either. For one thing this problem had 3 options so your only good "reason" to say I can't solve these tricky problems with logic. Now what you said about guessing is a better strategy then logic is untrue, you see you may call it randomly guessing, but you still have to choose one of them which implies that you are using some logic to take a guess, plus you said guessing is in fact a better strategy without real data to prove it. So is it really flawed logic, or can you not wrap your head around someone going outside the box and finding a solution in a different way?
They both can!
Bonus: Prove that K 5 is not planar and that K 8 is not toroidal.