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

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Can you draw a figure from $(K_{3,3})$ with thickness=2 ?? $\endgroup$
    – World
    Nov 2, 2012 at 12:51
  • 1
    $\begingroup$ @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... $\endgroup$
    – gt6989b
    Nov 2, 2012 at 12:59
  • $\begingroup$ how to union of first subgraph and second subgraph is k3,3?(how to join first subgraph to second subgraph without crossing edges? $\endgroup$
    – World
    Nov 2, 2012 at 13:16
  • $\begingroup$ @World You cannot draw $K_{3,3}$ without crossing edges in the plane. But each of the individual two subgraphs would be planar. $\endgroup$
    – gt6989b
    Nov 2, 2012 at 13:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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