Homework Set Ia (1/28)

Hand in Thurs., 1/29:
## AA1, AA2.
Do at least parts (a); do more if you can in a reasonable amount of time. Don't spend a lot of time on these questions.

Problem Set AA

AA1. This problem concerns ways of testing graphs for being isomorphic or nonisomorphic. In each part, suppose G and H are isomorphic graphs.

1. Show that |E(G)| = |E(H)|.
2. Show that either G and H are both connected, or they are both disconnected.
3. Show that G and H have the same degree sequence.

The point is that, if G and H are graphs that fail any one of these properties, then they cannot be isomorphic (by contradiction). But the converse is not true, as the next problem shows.

AA2. For each property in # 1, find a pair of graphs, G and H, that are not isomorphic but which fail the property. Specifically, do these:

1. Find G and H that have the same number of edges.
2. Find G and H that are both connected and have the same number of edges. Also, find G and H that are both disconnected and have the same number of edges.
3. Find G and H that have the same degree sequence and are both connected.