5
$\begingroup$

Suppose we are given a cube and we add a pair of crossing edges inside each of its faces. It is clear that this drawing has 6 crossings. My question is whether such a graph has crossing number 6? How to prove or disprove it?

(there is a new question below)

What is the crossing number of dodecahedron with a copy of $K_5$ inside each face

Improve this question
$\endgroup$
4
  • $\begingroup$ Thanks the answer from Noam D. Elkies. Now I want to update my problem. Suppose we are given a regular dodecahedron. Then we add five crossed edges inside each of its faces (actually, inside each face it is a copy of $K_5$). It is clear that this drawing has 60 crossings. My question now is whether such a graph has crossing number 60? How to prove or disprove it? $\endgroup$
    – Xin Zhang
    Commented Nov 8, 2020 at 5:10
  • $\begingroup$ Do you mean $K_4$ in the title? $\endgroup$
    – Brendan McKay
    Commented Nov 8, 2020 at 6:05
  • $\begingroup$ @BrendanMcKay It is $K_5$ for the updated question and $K_4$ for the original question. $\endgroup$
    – Tony Huynh
    Commented Nov 8, 2020 at 7:19
  • 3
    $\begingroup$ @XinZhang I think the standard procedure is to accept the answer to your original question and ask your new question as a separate question. $\endgroup$
    – Tony Huynh
    Commented Nov 8, 2020 at 7:20

1 Answer 1

Reset to default
8
$\begingroup$

Yes, the crossing number is $6$.

In general if a graph with $V$ vertices and $E$ edges can be drawn without crossings then $E \leq 3V-6$, by a familiar application of Euler's formula $V-E+F = 2$: there are $F = E-V+2$ faces; but each edge separates $2$ faces while each face has at least $3$ sides; so $$ 2E \geq 3F = 3(E-V+2) = 3E - (3V-6), $$ whence $E \leq 3V-6$ as claimed.

Now if the graph can be drawn with $c$ crossings then we can remove $c$ of the edges to obtain a graph with $V$ vertices, $E-c$ edges, and a crossing-free drawing. Therefore $c \geq E - 3V + 6$.

Your graph has $V=8$ and $E=24$, so $c \geq 24 - 3 \!\cdot\! 8 + 6 = 6$, QED.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .