(Brian Thomas rhea HW#13 (due 12/4/2008)) |
|||
| Line 3: | Line 3: | ||
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. | 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. | 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. | ||
| + | |||
| + | ---- | ||
| + | |||
| + | Rephrasing the problem may make it simpler. Say that we have a connected simple graph G with e edges, v vertices, and thickness n. We need to show, then, that <math>n \geq \frac{e}{3v-6}</math>. | ||
| + | |||
| + | We know each subgraph <math>G_i</math> is simple and planar. If each was connected, we could then conclude that for each graph <math>G_i</math>, the number of edges <math>e_i</math> that it contains is <math>e_i \leq 3v-6</math>. Since every edge needs to be covered in at least one subgraph, <math>\sum_{i=1}^n e_i \geq e</math>. | ||
| + | |||
| + | So, we have: <math>e \leq \sum_{i=1}^n e_i \leq \sum_{i=1}^n (3v-6) \leq n (3v-6) \Rightarrow n \geq \frac{e}{3v-6}</math>. | ||
| + | |||
| + | However, this assumes each subgraph <math>G_i</math> is connected, which certainly is not necessarily true. Can anybody think of a way to resolve this? Post something below if you can! | ||
| + | |||
| + | --[[User:Thomas34|Thomas34]] 18:46, 3 December 2008 (UTC) | ||
| + | |||
| + | ---- | ||
| + | |||
| + | [Patiently awaiting responses...] | ||
Revision as of 13:46, 3 December 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.
Rephrasing the problem may make it simpler. Say that we have a connected simple graph G with e edges, v vertices, and thickness n. We need to show, then, that $ n \geq \frac{e}{3v-6} $.
We know each subgraph $ G_i $ is simple and planar. If each was connected, we could then conclude that for each graph $ G_i $, the number of edges $ e_i $ that it contains is $ e_i \leq 3v-6 $. Since every edge needs to be covered in at least one subgraph, $ \sum_{i=1}^n e_i \geq e $.
So, we have: $ e \leq \sum_{i=1}^n e_i \leq \sum_{i=1}^n (3v-6) \leq n (3v-6) \Rightarrow n \geq \frac{e}{3v-6} $.
However, this assumes each subgraph $ G_i $ is connected, which certainly is not necessarily true. Can anybody think of a way to resolve this? Post something below if you can!
--Thomas34 18:46, 3 December 2008 (UTC)
[Patiently awaiting responses...]
