9
$\begingroup$

You are given a round ball and a marker pen. Your task is to draw $K_8-C_4$ on the ball – the complete graph on 8 vertices labelled 0 to 7, but with the edges 0-1,1-2,2-3,3-0 removed, thus 24 edges – such that no two edges cross except at up to two designated crossing points.

Any number of edges may pass through each crossing point, but they must pass straight through, i.e. if a small circle of positive radius is drawn around the point, edges must enter and leave the circle at antipodes.

Can you draw the graph with the above conditions and at least twofold rotational symmetry?

Bonus: Can you draw the graph on a coffee mug without any crossings?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ You may present your problem in a way that adds two nodes and doubles some of the edges. And it could be also defined as a 2D problem - I do not see the significance of the ball. $\endgroup$
    – Moti
    Commented Oct 7 at 5:16
  • $\begingroup$ @Moti Had I said "sheet of paper" rather than "ball" I would not have been able to include the symmetry requirement. $\endgroup$
    – Parcly Taxel
    Commented Oct 7 at 6:39
  • $\begingroup$ This is equivalent to drawing the $K_8-C_4$ on a Klein bottle, represented as a sphere with two cross-caps which are then flattened. $\endgroup$
    – Magma
    Commented Oct 9 at 17:21

2 Answers 2

Reset to default
10
$\begingroup$

Ball with rotational symmetry:

24-edge graph on a ball, with two crossings

Improve this answer
$\endgroup$
4
$\begingroup$

Bonus:

The Euler characteristic of a coffee mug is V - E + F = 0, so any drawing of the graph would have 24 - 8 = 16 faces. For each face, the number of edges that it borders is at least 3, so the sum of this quantity over all faces is at least 3 x 16 = 48. Each edge borders 2 faces, so this sum is in fact exactly 2 x 24 = 48. Therefore, every face is a triangle.

Consider the neighborhood of the 0-2 edge. Up to renumbering, it must look like this:

Graph with vertex 0 and neighboring vertices 4, 2, 5, 7, and 6 in clockwise order forming triangles. Vertex 2 also forms triangles with its clockwise neighbors 5, 0, 4, and extra copies of 7 and 6.

Imagine standing on the 6-7 edge with 6 on your left and 7 on your right. Then the third vertex of the face you face could be 0 or 2, so the surface is not orientable. Therefore, drawing the graph on a coffee mug without crossings is impossible.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.