On 2D Inverse Problems/6

A small correction: the theorem is usually stated as: > Every finite simple planar graph has at least one vertex of degree **at most 5**. It does **not** mean every vertex has degree ≤ 5. For example, a star graph is planar, and its center can have very high degree. Why there must be a vertex of degree ≤ 5 Let the planar graph have \(V\) vertices and \(E\) edges. For a simple planar graph with \(V \ge 3\), Euler’s formula says: \[ V - E + F = 2 \] where \(F\) is the number of faces. In a simple planar graph, every face is bounded by at least 3 edges. Also, each edge borders at most 2 faces, so: \[ 3F \le 2E \] Using Euler’s formula, this gives: \[ E \le 3V - 6 \] Now suppose, for contradiction, that every vertex had degree at least 6. Then the sum of all degrees would be at least \(6V\). But the sum of degrees equals \(2E\), so: \[ 2E \ge 6V \] which means: \[ E \ge 3V \] But this contradicts the earlier bound: \[ E \le 3V - 6 \] So it is impossible for every vertex to have degree at least 6. Therefore, at least one vertex must have degree: \[ \le 5 Intuition Planar graphs cannot be too dense. They have at most about \(3V\) edges, so their average degree is less than 6. Since the average degree is below 6, at least one vertex must have degree 5 or less. This fact is important in proofs such as the 6-color theorem for planar graphs.