Let's work through your graph theory questions clearly—first covering how to prove planarity when given vertex count and boundary edge conditions, then solving the specific 12-vertex graph problem you mentioned.

To determine if a graph is planar, you’ll rely on two core tools: Euler’s Formula and planarity-specific necessary inequalities (if these fail, the graph is definitely non-planar; if they hold, you can dig deeper with Kuratowski’s Theorem or construct a planar embedding).

Key Tools: #

• Euler’s Formula (for connected planar graphs):
  n - m + r = 2
  Where n = number of vertices, m = number of edges, r = number of regions (including the outer infinite region).
• Handshaking Lemma:
  2m = Σdeg(v) (sum of vertex degrees equals twice the number of edges—useful if you know vertex degree constraints).
• Edge-Region Relationship:
  If every region has at least k boundary edges, then kr ≤ 2m (each edge is shared by 2 regions).
• Planarity Inequalities:
  • For simple planar graphs (no loops, no multiple edges): m ≤ 3n - 6 (derived from assuming every region has at least 3 edges).
  • For graphs where every region has at least k edges: m ≤ k(n-2)/(k-2) (generalized from the 3-edge region case).

General Proof Steps: #

1. Use your given boundary edge/vertex conditions to relate m, n, and r (via the handshaking lemma or edge-region relationship).
2. Plug these into Euler’s Formula to solve for unknowns (if needed).
3. Check if the graph satisfies the relevant planarity inequality. If not, it’s non-planar.
4. If it does satisfy the inequality, either:
   • Construct an explicit planar embedding of the graph, or
   • Prove it contains no subdivisions of K₅ (complete graph on 5 vertices) or K₃,₃ (complete bipartite graph on 3+3 vertices) (per Kuratowski’s Theorem).

Let’s calculate edge count, region count, and verify planarity step by step.

Step 1: Calculate Edge (m) and Region (r) Counts #

We start with two critical relationships:

1. Edge-Region Link: Every region has 4 boundary edges, and each edge is shared by exactly 2 regions. This gives us:
   4r = 2m → Simplifies to m = 2r
2. Euler’s Formula: We know n = 12 (vertex count). Substitute m = 2r into the formula:

   12 - 2r + r = 2
   12 - r = 2
   r = 10
   

   Now plug r = 10 back into m = 2r: m = 2*10 = 20

So this graph has 20 edges and 10 regions.

Step 2: Prove Planarity #

We’ll use the planarity inequality for graphs where every region has at least 4 edges:
m ≤ 4(n-2)/(4-2)

Let’s compute the right-hand side:
4*(12-2)/2 = 4*10/2 = 20

Our graph has m = 20, which exactly equals the upper bound of this inequality. This tells us the graph meets the tight condition for a planar graph (it’s a 4-face-regular planar graph—every region is a 4-cycle).

We can double-check with the general simple planar inequality:
3n - 6 = 3*12 - 6 = 30
Since 20 ≤ 30, this also holds.

For full confirmation, since the graph satisfies the necessary and sufficient condition for this class of planar graphs (equality in the k-region edge inequality), we can definitively say it is planar. You could even construct such a graph—think of a grid-based planar graph where all internal regions are squares, adjusted to have exactly 12 vertices total.

内容的提问来源于stack exchange，提问作者Epicurean Segal