Homework Set II (1/24, 26)

ADDED: Due Tues., 1/25:
Read all of Sections 1.1 and 1.2.

Hand in Fri., 1/28:
## B1(a,b), B2(a,b).

Due Fri., 1/28:
Do for discussion: ## B1(c), B2(c) (think about them for a few minutes; we'll discuss them in class). Correction: Parts (c) are the degree-sequence questions.

Problem Set B

B1. 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.

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

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.

Grading of hand-in HW

• B1(a). You can't just say G and H must have the same degree sequence. If it were proved in section 1.2, you could use that, but they merely assert it's true.
• B1(b). (Connectedness.) A good method is to prove G connected implies H is connected. Then, by reversing the roles of G and H, you've also proved H connected implies G is connected.
  Assuming G is connected, you should prove H is connected by proving that any pair of vertices in H is joined by a path in H. You must state it correctly! Eg., it's not the same as saying there is a path to every vertex.
• B1(c). (Degree sequence.) Some did this instead of (b) because I got my labels mixed up. I accepted this if proved correctly.
• Proofs by contradiction: Most of your proofs by contradiction would be easier if you didn't use contradiction. If you want to prove A implies B, often it's easier to assume A and just prove B is true.
• B2(a). I gave separate grades for a valid example and a proof that the example is valid. Normally you should prove your examples are valid.
• B2(b). But here I didn't worry about proof, just to keep things simpler. I gave 2 points per part so the total would be 4 (one full grade). If you only answered one part, you got at most 2 points.
• B2(c). Again, some answered this instead of (b). That's okay; it was my fault.