Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 8] GRAPH THEORY 163

Fig. 8-13

Fig. 8-14

Fig. 8-15

Bipartite Graphs

A graphGis said to bebipartiteif its verticesVcan be partitioned into two subsetsMandNsuch that each
edge ofGconnects a vertex ofMto a vertex ofN. By a complete bipartite graph, we mean that each vertex of
Mis connected to each vertex ofN; this graph is denoted byKm,nwheremis the number of vertices inMand
nis the number of vertices inN, and, for standardization, we will assumem≤n. Figure 8-16 shows the graphs
K 2 , 3 ,K 3 , 3 , andK 2 , 4 , Clearly the graphKm,nhasmnedges.