At the end of a proof you write Q.E.D, which stands not for
Quod Erat Demonstrandum as the books would have you believe, but
for Quite Easily Done.
-- R. Ainsley in Bluff your way in Maths, 1988
|
Euler's formula: A connected plane graph with n vertices, e edges and f faces
satisfies n - e + f = 2
Proof. Let T be the edge set of a spanning tree for G. It is a subset of the
set E of edges. A spanning tree is a minimal subgraph that connects all the
vertices of G. It contains so no cycle. The dual graph G* of G has a vertex
in the interior of each face. Two vertices of G* are connected by an edge if
the correponding faces have a common boundary edge. G* can have double edges
even if the original graph was simple. Consider the collection T* of edges
E* in G* that correspond to edges in the complement of T in E. The edges of
T* connect all the faces because T does not have a cycle. Also T* does not
contain a cycle, since otherwise, it would seperate some vertices of G
contradicting that T was a spanning subgraph and edges of T and T* don't
intersect. Thus T* is a spanning tree for G*. Clearly e(T)+e(T*)=2.
For every tree, the number of vertices is one larger than the number of
vertices. Applied to the tree T, this yields n = e(T)+1, while for the tree
T* it yields f=e(T*)+1. Adding both equations gives n+f=(e(T)+1)+(e(T*)+1)=e+2.
-- from M.Aigner, G. Ziegler "Proofs from THE BOOK"
|
