Information Technology Reference
In-Depth Information
Theorem 7.13. In any connected (finite) planar graph the following equation relat-
ing the numbers of its vertices, edges, and faces holds:
V
E
+
F
=
2
Proof. This formula trivially holds for the atomic connected graph, consisting of
only one node, where no edge is present, but one node and one face (the external
face) are present. Any (finite) planar connected graph can be constructed starting
from an atomic graph by applying, a certain number of times, two different pos-
sible operations (see Fig. 7.16): i) adding one node and one edge which connects
the new node to a node already in the graph, or ii) adding one edge which connects
two nodes already in the graph (which are connected by some path, but not already
directly connected by an edge). Of course, in both cases, the value V
F does
not change, because when we add one node we add also one edge, and when we add
only one edge we add also a face (because a new cycle is added to the graph). In con-
clusion, the value V
E
+
F is equal to 2 for the atomic graph and remains the same
after any of the two operations extending graphs. Therefore, the formula holds for
all connected planar graphs.
E
+
The dual graph G of a given planar graph G has as nodes the faces of G ,and
two nodes of G are connected by an edge if the corresponding faces of G share an
edge. An obvious property of planar graphs is that the dual graph of a planar graph
is planar too.
A simple relation concerning connected acyclic graphs (unrooted trees) is that
the number of vertices equals the number of edges plus 1. In fact, when a connected
acyclic graph is constructed, starting from the atomic graph, only the operation on
the left of Fig. 7.16 can be applied, because when a new node is added also a new
edge is added. Therefore, the node put at beginning of the construction is the only
one which does not introduce an edge. Hence, V
1.
A regular polyhedron is a convex polyhedron bounded by a number of equal
regular polygons (convex regions of plane bounded by segments (edges) with equal
lengths and forming equal angles). A famous geometrical proposition asserts that
only five different kinds of regular polyhedra exist ( hedron in Greek means face).
These polyhedra have been investigated by Plato (in the dialogue entitled Timaeus),
whereby they are referred to as the Platonic solids . The existence of only five Pla-
tonic solids can be proved as a consequence of Euler's polyhedral formula (a proof,
based on elementary geometry, is present in Euclid's books). We present this proof
as a paradigmatic example of an argument developed in purely mathematical dis-
crete terms, essentially based on the notion of planar graph.
=
E
+
Theorem 7.14 (Platonic solids). There are only five Platonic solids.
Proof. In a planar graph associated to regular polyhedron, two properties hold: the
degree g is the same for all nodes, and the number k of edges around a face is the
same for all faces ( k
>
2). These two facts imply the following equations:
gV
=
2 E
(7.28)
 
Search WWH ::




Custom Search