Easy Pizzzzi Graphs
Probability
Level
2
There is a graph with 145 vertices and 430 edges. Can the graph be planar ?
Nope
Yes always
May be... May be not !!
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
From the English Wikipedia article Planar graph : "In practice, it is difficult to use Kuratowski's criterion to quickly decide whether a given graph is planar. However, there exist fast algorithms for this problem: for a graph with n vertices, it is possible to determine in time O(n) (linear time) whether the graph may be planar or not (see planarity testing).
For a simple, connected, planar graph with v vertices and e edges and f faces, the following simple conditions hold for v ≥ 3:
Theorem 1. e ≤ 3v − 6; Theorem 2. If there are no cycles of length 3, then e ≤ 2v − 4. Theorem 3. f ≤ 2v − 4."
We were not given a face count; therefore, the third test can not be applied. We were not told anything about cycles of length 3; therefore, the looser test must be applied. Then, see Michael Zheng's solution for the completion of the argument.