1
$\begingroup$

The thickness of a simple graph G is the smallest number of planar subgraphs of G that have G as their union.

Show that K3,3 has 2 as its thickness.

My attempt:

[If we decompose K(3,3) into any pair of nonempty graphs A and B, the union of their edges make the edges of K(3,3), and A and B have no edges in common), then both A and B are planar. (Example: let A be one arbitrary edge of K(3,3) and let B be the rest.) It follows that the thickness of K(3,3) is no more than 2.]

It is enough? how to prove it more complete

1 Answers 1

1

This proves that thickness $\tau(K_{3,3})$ is at most $2$. To show that $\tau (K_{3,3}) >1$, note that $K_{3,3}$ itself is certainly not planar, so it's not possible to represent it as a union of 1 planar subgraph.

Thus, $2 \geq \tau (K_{3,3}) >1$, which implies $\tau (K_{3,3}) = 2$, since $\tau (K_{3,3})$ is an integer.

  • 0
    @World You cannot draw $K_{3,3}$ without crossing edges in the plane. But each of the individual two subgraphs would be planar.2012-11-02