7.02l–7.02o - Planar graphs | OCR A-Level Further Mathematics A

Decide whether connections can be drawn without crossings, and justify your answer. In $7.02l$ you will redraw graphs and use subdivision and contraction; in $7.02m$ you will count regions with Euler's formula; in $7.02n$ you will identify Kuratowski's obstructions; in $7.02o$ you will prove that a graph needs one or two planar layers.

Planar representations

Four terminals must each connect directly to the other three. A square drawing has crossing diagonals. Does that force two layers of wiring, or can one layer suffice? The crossing belongs to the drawing; we must find out whether it belongs to the graph.

You already know

An isomorphism preserves connections while vertex positions can change. $K_4$ has four vertices and all six possible arcs. Unmarked crossings are not extra vertices.

Move one of the square's vertices inside the triangle formed by the other three. The three outer arcs and the three connections to the inner vertex can now be drawn without any crossing.

[DIAGRAM: asset_name: A crossing drawing and a planar drawing of K4; asset_slug: h245_7_02_planar_k4; caption: Moving D inside triangle ABC removes the crossing without changing any connection; description: Left K4 is drawn on a square with crossing diagonals; right has outer triangle ABC and D strictly inside, joined to A B C. Both have precisely the six arcs AB AC AD BC BD CD.]

Planar graph

A graph is planar if it has a representation in the plane in which arcs meet only at their common end vertices. Such a drawing is a planar representation. Arcs may be curved. A crossing in one drawing does not prove that a graph is non-planar. This definition is not supplied in the formula booklet.

A redraw must preserve every connection. Moving an arc through another vertex would change the graph unless that vertex was already an end of the arc.

Worked example 1: redrawing a complete graph

Question. Describe a planar representation of the graph with arcs $AB, AC, AD, BC, BD, CD$ .

Plan. Use a triangle as the outside boundary and place the fourth vertex inside it.

\begin{aligned} \text{outer boundary}&:A,B,C,A && \text{draw }AB,BC,CA\\ \text{inner vertex}&:D && \text{strictly inside the triangle}\\ \text{inner arcs}&:DA,DB,DC && \text{join to each corner} \end{aligned}

Why this step? The three inner arcs share $D$ , so meeting there is permitted; none needs to cross an outer arc.

Answer. Draw triangle $ABC$ , put $D$ inside it and join $D$ to all three corners.

Check. All six required arcs appear once and no pair crosses away from a vertex.

The second example changes only one connection: remove $BC$ . A planar representation remains planar when an arc is deleted.

Worked example 2: deleting an arc

Question. Describe a planar representation of the graph with arcs $AB, AC, AD, BD, CD$ .

Plan. Start with the planar $K_4$ representation and remove the unwanted arc.

\begin{aligned} \text{start}&:\text{ triangle }ABC\text{ with inner vertex }D && \text{previous representation}\\ \text{delete}&:BC && \text{this arc is absent from the list}\\ \text{remaining arcs}&:AB,AC,AD,BD,CD && \text{check the complete list} \end{aligned}

Why this step? Deleting an arc cannot create a crossing, so no further rearrangement is required.

Answer. Use the previous drawing with arc $BC$ erased, retaining all four vertices.

Check. Removing an arc does not mean removing either of its end vertices.

The four-terminal puzzle therefore needs only one planar layer in this graph model. The terminals' physical positions might impose extra constraints in a real design, but they are free to move in the definition of planarity.

Watch out

Wrong: “The two diagonals cross, so $K_4$ is non-planar.” Right: the square drawing is not planar, but $K_4$ is planar because a crossing-free representation exists.

Use a different missing connection to check the construction.

Subdivision and contraction

Two operations change a graph in controlled ways. One inserts a junction along an existing connection; the other merges the ends of an existing connection.

Subdivision and contraction

To subdivide an arc $AB$ , insert a new degree-two vertex $X$ , replacing $AB$ by $AX$ and $XB$ . To contract arc $AB$ , merge its end vertices into one vertex labelled $(AB)$ , remove the contracted arc, and retain the other incidences at the merged vertex. Other arcs are not silently discarded: multiple arcs may result. These definitions and the notation $(AB)$ are not supplied in the formula booklet.

For example, contracting one side of a triangle leaves two arcs between the merged vertex and the third vertex. If a question asks for the underlying simple graph, it may then allow parallel copies to be replaced by one; that is a further simplification, not the contraction itself.

[DIAGRAM: asset_name: Subdivision and contraction of an arc; asset_slug: h245_7_02_subdivision_contraction; caption: Subdivision inserts a degree-two vertex; contracting its new arc restores the original connections; description: Three panels show triangle ABC, the triangle with AB replaced by AX and XB, and the contracted result with AX merged into (AX), joined to B and C while BC remains. Panel titles name subdivision of AB and contraction of AX.]
Subdivision inserts a degree-two vertex

Inserting a point on an arc of a planar drawing keeps it planar. Contracting an arc can be performed by shrinking that arc in a planar drawing, so it also preserves planarity. Conversely, a non-planar graph obtained by contraction proves that the original graph could not have been planar. This implication does not require you to merge arbitrary unconnected vertices. These planarity-preserving properties are not supplied in the formula booklet.

Worked example 3: a subdivision

Question. Triangle $ABC$ has arc $AB$ subdivided by $X$ . List the new arcs and state the numbers of vertices and arcs.

Plan. Replace the one arc $AB$ by its two successive pieces.

\begin{aligned} AB&\longrightarrow AX,XB && \text{insert the degree-two vertex}\\ \text{new arc list}&:AX,XB,BC,CA && \text{retain all other arcs}\\ V&=3+1=4,\qquad E=3+1=4 && \text{one new vertex and one net new arc} \end{aligned}

Why this step? The original $AB$ is replaced, not retained as a third connection.

Answer. The arcs are $AX,XB,BC,CA$ , with $4$ vertices and $4$ arcs.

Check. Vertex $X$ has degree two, and the planar triangle drawing just gains a point on a side.

The second example reverses this one local change by contracting one of the two new pieces.

Worked example 4: contracting a subdivided arc

Question. Contract $AX$ in the graph with arcs $AX,XB,BC,CA$ . Give the resulting vertices and arcs.

Plan. Merge $A,X$ into $(AX)$ , delete $AX$ , and rename every remaining incidence.

\begin{aligned} A,X&\longrightarrow(AX) && \text{merge the ends}\\ XB&\longrightarrow(AX)B && \text{rename }X\\ CA&\longrightarrow C(AX) && \text{rename }A\\ BC&\longrightarrow BC && \text{neither end is merged} \end{aligned}

Why this step? Both original vertices become the same new vertex, so every remaining incident arc must follow them.

Answer. The vertices are $(AX),B,C$ , with arcs $(AX)B,BC,C(AX)$ .

Check. This is a triangle again, with one fewer vertex and one fewer arc than before contraction.

An ordinary subdivision adds one to both $V$ and $E$ . A contraction of a non-loop arc subtracts one from each before any additional simplification. These counts are consequences of the definitions and are not printed in the formula booklet.

Watch out

Wrong: “Contract $AB$ by deleting $A$ and all its arcs.” Contraction transfers its other connections to $(AB)$ ; deleting them changes a different graph.

Contract an arc in a different cycle.

Euler's formula and regions

A planar representation divides the plane into regions. The unbounded region outside the drawing counts too. For the planar $K_4$ drawing there are three small triangular regions and one outside region.

[DIAGRAM: asset_name: Four regions of a planar K4; asset_slug: h245_7_02_euler_regions; caption: Three bounded regions and the outside region give R = 4; description: Triangle ABC contains D joined to all corners. Its three bounded triangular faces are lightly filled and labelled R1 R2 R3; R4 is labelled outside the triangle. A side calculation states V=4 E=6 and 4+4=6+2.]

Euler's formula

For a finite connected planar graph, in a planar representation,

V+R=E+2

where $V$ counts vertices, $E$ arcs and $R$ all regions, including the unbounded outside region.
Not in the formula booklet: learn it.

Why does it work? A tree has $E=V-1$ and only the outside region, so the formula holds. In a connected planar graph with a cycle, delete an arc on a cycle: this keeps the graph connected and merges two regions, reducing $E$ and $R$ by one each. Continue until a tree remains. The quantity $V+R-E$ stays unchanged throughout, so its original value is also two. Bridges are different: deleting one disconnects the graph, so do not use a bridge in that argument.

Worked example 5: finding the number of regions

Question. A connected planar graph has $7$ vertices and $11$ arcs. Find the number of regions in a planar representation.

Plan. Substitute the supplied counts into Euler's formula.

\begin{aligned} 7+R&=11+2 && V+R=E+2\\ R&=6 && \text{subtract seven} \end{aligned}

Why this step? The formula counts all regions, so do not add the outside region after calculating.

Answer. There are $6$ regions, including the outside region.

Check. Five are bounded, and $7+6=11+2$ .

The second example changes only which count is unknown: regions are given and arcs must be found.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

Last Accessed

Pure Core

Statistics

Mechanics

Discrete Mathematics

Additional Pure Mathematics

7.02l–7.02o - Planar graphs

Planar representations

Subdivision and contraction

Euler's formula and regions

Continue this lesson.

Learn faster with Nova