136 CHAPTER 2 Discrete Mathematics
The next important family involves
the so-called bipartite graphs.
The simple graph G is called bi-
partiteif its set V of vertices can
be partitioned into two disjoint sub-
setsV =V 1 ∪V 2 where there are no
edges among the vertices ofV 1 and
there are no edges among the ver-
tices ofV 2.
Thecomplete bipartite graphKm,n, wheremandnare positive
integers, is the bipartite graph with verticesV =V 1 ∪V 2 ,|V 1 |=mand
|V 2 |=nand where every vertex ofV 1 is adjacent with every vertex of
V 2 (and vice versa).
We turn now to the main topic of this section, that of planar
graphs.^37 These are the graphs which can be “faithfully” drawn in
the plane. By “faithful” we mean that the edges drawn between ver-
tices will have no crossings in the plane. As a simple example, we
consider below two versions of the graph of the cube: the first is how
we usually imagine it in three-dimensional space, and the second is how
we could draw it in the plane.
Example 1. The complete graphs K 1 , K 2 , K 3 , K 4 are obviously pla-
nar graphs. However, we shall see below thatK 5 is not planar; in fact,
none of the complete graphsKn, n≥5 is planar. Also, the complete
bipartite graphK 3 , 3 is also not planar (try it!). (We’ll prove below that
K 3 , 3 is not planar.)
(^37) The topic of Planar graphs falls into the general category of “topological graph theory.”