DA3 - Euler’s formula for planar graphs
A planar graph can be drawn with no crossing edges, and such a drawing divides the plane into faces. Learn to count those faces, including the outside region, and use Euler's formula to link them to vertices and edges. You will then derive edge bounds that can prove a graph non-planar.
Planar drawings and faces
A square has a diagonal, and a single extra edge extends outwards from one corner to a new vertex. How many regions does the drawing make, including the outside? The extending edge looks like a new boundary, but it does not close a new region.
A graph is planar if it has at least one drawing in the plane in which edges meet only at their shared endpoint vertices. Such a drawing is a plane embedding. Curved edges are allowed. One drawing with crossings does not prove non-planarity: a different placement or curved edge may remove them. The graph , for example, can be drawn as a triangle with its fourth vertex inside, joined to all three corners, even though a square with both diagonals gives a crossed drawing of the same graph.
A face is a connected region of the plane left by a plane embedding. Count the unbounded exterior face once. A triangle has two faces, its inside and outside. A tree has one face: every space around its branches connects to the outside. Faces are counted from a drawing without crossings; arbitrary regions of a crossed sketch are not automatically faces of a plane embedding of the graph.
[DIAGRAM: asset_name: Faces in plane embeddings; asset_slug: aqa7367-planar-faces; caption: The square with a diagonal has three faces while the tree has one; description: Left has square ABCD with diagonal AC, two interior faces labelled F1 F2 and the exterior labelled F0. Its counts are V four E five F three. Right is a tree with vertices A B C D and edges AB BC BD, with V four E three F one.]
A face's boundary may use an edge twice. An edge whose removal disconnects a connected graph is a bridge. Its two sides border the same face: walking all the way round that face crosses the bridge outwards and back. Therefore counting boundaries means counting edge sides, rather than just distinct edges.
Worked example 1: including the exterior
Question. A square ABCD is drawn without crossings and has diagonal AC inside it. Find its number of faces and the total length of all face boundaries.
Plan. Count the two enclosed triangles and the exterior; count each boundary's edge occurrences.
The two inside boundaries ABC and ACD each have length 3. The exterior boundary ABCD has length 4.
Answer. Three faces, with total boundary length 10.
Check. There are five edges, each with two face sides, giving .
Add just one outward edge DE to a new vertex E. It does not enclose a region, but does contribute two sides to an existing boundary.
Worked example 2: an edge that creates no face
Question. Add outward pendant edge DE to the square-and-diagonal embedding. Find its face count and boundary-length total.
Plan. Keep the two triangular faces and trace the changed exterior boundary.
There are still two bounded faces and one exterior. The exterior walk now takes a detour D–E–D along the bridge, increasing its length from 4 to 6.
Answer. Three faces; the boundary-length total is 12.
Check. The graph now has six edges, so its twelve edge sides have all been counted.
For a disconnected embedding there is still just one unbounded face. Two disjoint triangles have two bounded interiors and one exterior, giving three faces, not four. Even if one triangle is drawn inside the other, the regions are the inner triangle, the annulus between triangles, and the exterior: still three.
Watch out
Include the exterior once. A bridge creates no new face, and its two sides belong to the same face. Count only explicitly marked points as vertices; a crossed sketch must be redrawn before its regions are used as faces.
Count fresh regions without assuming that every new edge creates one.
Euler’s formula and connected components
Vertices, edges and faces can change separately, but a connected plane embedding always preserves the same combination of their counts.
Euler’s formula
For a finite connected planar graph, in any plane embedding,
where includes the exterior face. Euler's graph formula is not printed in the exam formula booklet; it must be recalled.
To understand why it works, start with a connected plane embedding. Remove an edge on a cycle: it separates two faces, which merge, so E and F each decrease by one. Connectedness remains because the rest of the cycle still joins the edge's endpoints. Repeat until a tree remains. The tree has and one face, so . Each removal left this combination unchanged, proving the original formula too. Removing a bridge would break this argument, so we remove cycle edges only.
Rearrange for the unknown rather than memorising three separate rules:
Worked example 3: finding the face count
Question. A connected planar graph has nine vertices and twelve edges. Find its number of faces.
Plan. Use Euler's formula with the exterior included.
Answer. Five faces in total, of which four are bounded.
Check. Substitution gives . Compared with a tree on nine vertices, the four extra edges account for four extra faces.
Now encode the counts by an integer parameter. The equation can produce an algebraic candidate that the graph conditions reject.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account