| 4. |
(a) Find the adjacency
matrix for |
|
|
|
(i) K4,
the complete graph on four vertices. |
[3] |
|
|
(ii) K2,3
the complete bipartite graph on (2,3) vertices. |
[3] |
|
|
|
|
|
(b) Show
that the following pairs of graphs are not isomorphic by finding an isomorphic invariant
that they do not share. |
|
|
|
(i) |
|
[2] |
|
|
(ii) |
|
[2] |
|
|
|
|
(c) Show that the two
graphs below are isomorphic by finding the two functions |
|
|
|
g : V( G ) ®
V( G' ) |
|
|
|
h : E( G ) ® E( G' ) |
|
|
by
drawing the arrow diagrams, such that, for all v Î V(G) and e Î E(G) , v is an endpoint of e iff g(v) is an endpoint
of h(e). |
[5] |
|
|
|
|
|
|
|
(d) Redraw the
following bipartite graphs, so that their bipartite natures are evident. |
[5] |
|
|
|