490
Graphs and Trees
can count the number of edges that are adjacent to (form the boundaries of) each region, including the exterior region. Arcs that are wholly interior to a region contribute
two edges to that region; for example, if we trace the boundary of the interior region
shown in Figure 6.22b, we travel six edges, including the arc out to the node of degree
1 and then back again. Arcs that separate two regions contribute one edge to each
region. Therefore, if there are a arcs in the graph, the number of region edges is 2a.
There are no regions with exactly one adjacent edge, because there are no
loops in the graph. There are no regions with exactly two adjacent edges, because
there are no parallel arcs and the graph consisting entirely of one arc joining two
nodes (which would have two edges adjacent to the exterior region) is excluded.
Therefore each region has at least three adjacent edges, so 3r is the minimum
number of region edges. Thus
2a ≥ 3r
or, from Equation (1),
2a ≥ 3(2 − n + a) = 6 − 3n + 3a
and finally
a ≤ 3n − 6
(2)
If a final restriction that there are no cycles of length 3 is placed on the graph,
then each region has at least four adjacent edges, so 4r is the minimum number of
region edges. This leads to the inequality
2a ≥ 4r
which becomes
a ≤ 2n − 4
(3)
These results are summarized in the following theorem.
tHeorem on The numBer oF noDes anD arcs
For a simple, connected, planar graph with n nodes and a arcs:
1. If the planar representation divides the plane into r regions, then
n − a + r = 2
(1)
2. If n ≥ 3, then
a ≤ 3n − 6
(2)
3. If n ≥ 3 and there are no cycles of length 3, then
a ≤ 2n − 4
(3)
Note that inequality (3) places a tighter bound on the number of arcs than inequality
(2), but an additional condition has been imposed on the graph.
We can use this theorem to prove that certain graphs are not planar.
Graphs and Trees
can count the number of edges that are adjacent to (form the boundaries of) each region, including the exterior region. Arcs that are wholly interior to a region contribute
two edges to that region; for example, if we trace the boundary of the interior region
shown in Figure 6.22b, we travel six edges, including the arc out to the node of degree
1 and then back again. Arcs that separate two regions contribute one edge to each
region. Therefore, if there are a arcs in the graph, the number of region edges is 2a.
There are no regions with exactly one adjacent edge, because there are no
loops in the graph. There are no regions with exactly two adjacent edges, because
there are no parallel arcs and the graph consisting entirely of one arc joining two
nodes (which would have two edges adjacent to the exterior region) is excluded.
Therefore each region has at least three adjacent edges, so 3r is the minimum
number of region edges. Thus
2a ≥ 3r
or, from Equation (1),
2a ≥ 3(2 − n + a) = 6 − 3n + 3a
and finally
a ≤ 3n − 6
(2)
If a final restriction that there are no cycles of length 3 is placed on the graph,
then each region has at least four adjacent edges, so 4r is the minimum number of
region edges. This leads to the inequality
2a ≥ 4r
which becomes
a ≤ 2n − 4
(3)
These results are summarized in the following theorem.
tHeorem on The numBer oF noDes anD arcs
For a simple, connected, planar graph with n nodes and a arcs:
1. If the planar representation divides the plane into r regions, then
n − a + r = 2
(1)
2. If n ≥ 3, then
a ≤ 3n − 6
(2)
3. If n ≥ 3 and there are no cycles of length 3, then
a ≤ 2n − 4
(3)
Note that inequality (3) places a tighter bound on the number of arcs than inequality
(2), but an additional condition has been imposed on the graph.
We can use this theorem to prove that certain graphs are not planar.