| (4 intermediate revisions by 2 users not shown) | |||
| 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. | ||
| + | |||
| + | ---- | ||
| + | |||
| + | 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) | ||
| + | |||
| + | ---- | ||
| + | |||
| + | "v" must be greater than two because of dividing by a negative number, thereby resolving the connectedness problem? | ||
| + | -I don't have time to check. Quickly saw something, but would like to have someone else look this over. | ||
| + | |||
| + | |||
| + | [Patiently awaiting responses...] | ||
| + | |||
| + | ---- | ||
| + | You don't need to show anything is connected because it is given that G is connected. Since <math>n >= 1</math>, and (for <math>v>=3</math>) we know that <math>e/(3v-6) <=1</math> so <math>n>=1>=e/(3v-6)</math> | ||
Latest revision as of 04:58, 4 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)
"v" must be greater than two because of dividing by a negative number, thereby resolving the connectedness problem? -I don't have time to check. Quickly saw something, but would like to have someone else look this over.
[Patiently awaiting responses...]
You don't need to show anything is connected because it is given that G is connected. Since $ n >= 1 $, and (for $ v>=3 $) we know that $ e/(3v-6) <=1 $ so $ n>=1>=e/(3v-6) $
