MATH 224 Homework VII

This homework is due at the beginning of class on Tuesday, December 8.

For all questions in this homework, assume that the vertex set of the graphs G1, G2, G3, G4, G5, and G6 is the same vertex set V = {Alice, Bob, Candice, Darron, Eric}. The edge sets of these graphs are defined as follows:

1. Draw all six graphs G1, G2, G3, G4, G5, and G6.

3. Pick any three of the six graphs and draw the adjacency matrix of the graphs that you select.

2. There is exactly one pair of graphs Gi and Gj (i ≠ j) that are isomorphic to each other. State the pair along with an isomorphic map between them, namely a mapping f : V → V of the vertices Gi to the vertices of Gj such that u and v are adjacent in Gi if and only if f(u) and f(v) are adjacent in Gj.

4. For each of the six graphs G1, G2, G3, G4, G5, and G6, state the degree distribution vector degrees = < degree(Alice), degree(Bob), degree(Candice), degree(Darron), degree(Eric) >.

5. There is exactly one graph that is isomorphic to the complete graph K5. Which one is it?

6. using the degree distributions that you already calculated, argue as to why no other pair of graphs (aside from those you answered in question two) could be isomorphic to each other.