| Line 2: | Line 2: | ||
Ditto. | Ditto. | ||
| + | |||
| + | --- | ||
| + | |||
| + | So. First we have to figure out what "thickness" means. The book defines thickness of a simple graph G as the smallest number of planar subgraphs of G that have G as their union. This means that if a graph is planar, its thickness is one. However if a graph is not planar, then we have to figure out how many different graphs we have to divide it into in order to make each individual subgraph to be planar. | ||
| + | |||
| + | As a hint for this problem, find a formula that relates edges and vertices with simple graphs. Once you find a couple, the proof shouldn't be that bad as long as you really know what thickness means. | ||
Revision as of 11:55, 30 November 2008
Can someone explain this problem?
Ditto.
---
So. First we have to figure out what "thickness" means. The book defines thickness of a simple graph G as the smallest number of planar subgraphs of G that have G as their union. This means that if a graph is planar, its thickness is one. However if a graph is not planar, then we have to figure out how many different graphs we have to divide it into in order to make each individual subgraph to be planar.
As a hint for this problem, find a formula that relates edges and vertices with simple graphs. Once you find a couple, the proof shouldn't be that bad as long as you really know what thickness means.
