Tip:
Highlight text to annotate it
X
Now we're going to use Euler's formula to give us a handle on how fast edges grow
relative to the number of nodes in a planar graph.
We're going to make use of two other facts.
One is that every region in a planar graph has to be encapsulated--has to be bounded--
by at least three edges for it to be a region.
It might be more that that, but it has to be at least three.
If you think about three times the number of regions,
the number of edges has to be at least that big, though, we're counting each edge twice,
because each edge can actually participate in two regions.
Twice the number of edges has to be bigger than or equal to three times the number of regions.
Rewriting Euler's formula, we have this--rewriting this equation, we have this.
Substituting in, we have this.
Let's multiply through by 3. We get 3m + 6 ≤ 3n + 2m.
Subtract m from both sides and subtract 6 from both sides, a
and we get m, the number of edges, can't be any bigger than 3n - 6,
which this expression is in Θ(n).
The most edges that we can have in a planar graph is at most linear in the number of nodes.