Math 2602 A1, A2, A3
Homework #7
Due Tuesday, March 11, 2003
1. For each graph find the "clique number"
(p. 211) and the "chromatic number" (p.257).
(i) The complete graph K
10 .
(ii) The complete bipartite graph K
5,5. ( see p.214.)
(iii) The graph with the adjacency matrix
below.
A B
C D
E F
G H
A
0 1
0 0
1 0
1 1
B
1 0
1 1
1 0
0 1
C
0 1
0 1
0 0
0 0
D
0 1
1 0
1 1
0 0
E
1 1
0 1
0 1
0 0
F
0 0
0 1
1 0
1 0
G
1 0
0 0
0 1
0 1
H
1 1
0 0
0 0
1 0