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
    Can you draw a figure from $(K_{3,3})$ with thickness=2 ??2012-11-02
  • 1
    @World Not sure I understand what you are asking. For example, let the partitions be $\{a,b,c\},\{x,y,z\}$ and let the first subgraph be the edges $\{a,x\},\{a,y\},\{a,z\}$, while the second subgraph will have all other edges (picture $b$ at $(-1,0)$, then $x,y,z$ on $(0,1), (0,0), (0,1)$ and $c$ at $(1,0)$), as this is $K_{2,3}$ it is clearly planar. Put the vertex $a$ anywhere else, and the $3$ edges of the first graph are planar as well...2012-11-02
  • 0
    how to union of first subgraph and second subgraph is k3,3?(how to join first subgraph to second subgraph without crossing edges?2012-11-02
  • 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