Discrete Mathematics for Computer Science

Introduction to Graph Theory 335

regular graph is n-regular if each vertex has degree n. Graphs that are 3-regular are often

called cubic graphs.

Some examples of complete graphs and regular graphs are shown in Figure 6.5.

K, K 2 K 3 K 4 K 5

2-regular 3-regular 4-regular

Figure 6.5 Complete and regular graphs.

Another family of graphs that are used in matching problems, resource allocation prob-

lems, and computer architecture modeling is the family of bipartite graphs.

Definition 3. Let G = (V, E) be a graph. G is a bipartite graph if its vertex set V

can be partitioned into two nonempty disjoint subsets V 1 and V 2 , called a bipartition, so

that each edge has one end in V 1 and one end in V 2 .A complete bipartite graph is a

bipartite graph with bipartition V1 and V 2 in which each vertex of V 1 is joined by an edge

to each vertex of V 2 .A complete bipartite graph with I V1i = m and I V 2 I = n is denoted

as Km,n.

Examples of bipartite graphs and the bipartitions they determine are shown in
Figure 6.6.

V, V2 1 4 4

1• 2 56 2•

x2 4 *

3 6 3

7

K 2 , 2 K 3 ,3 K 3 ,4

V 1 and V 2 V = 1 {1,2} V 1 = {1, 2,3} V 1 = {1, 2,31

forma V 2 = {3,4) V 2 = {4,5,6} V 2 = {4, 5, 6,^71

bipartition

Figure 6.6 Bipartition and complete bipartite graphs.