Solutions to HW8

1. Ex 6.1.4

  1. "a taller than b"
    - transitive
    - anti-symmetric (because (a,b) and (b,a) never happen together) (the relation is assymetric)

  2. "born on the same day"
    - reflexive
    - symmetric
    - transitive

  3. "same first name"
    - reflexive
    - symmetric
    - transitive

  4. "common grandparent"
    - reflexive
    - symmetric
    not transitive (think of cousins)

2. Ex. 6.5.10

It is easy to check that the relation is reflexive, transitive, and symmetric.

3. Ex. 6.5.24

  1. [(1,2)] = {(a,b) | 2a = b}
  2. Since ad = bc iff a/b = c/d, it is easy to see that each equivalence class corresponds to a rational number. E.g., [(1,2)] = [(2,4)] = 0.5

4. Ex. 6.10 p433

We need to show two things:
  1. circular and reflexive => equivalence relation
  2. equivalence relation => circular and reflexive

  1. In the first case we have: R is circular and R is reflexive. We only need to show that R is symmetric and transitive. Then R must be an eq relation.

    Let aRb. Since R is reflexive, aRa. Since R is circular aRa ^ aRb => bRa. Hence R is symmetric.

    Let aRb and bRc. Since R is circular, cRa. We've shown that R is symmetric. Hence, aRc and R is transitive.

    Therefore, R is an equivalence relation.

  2. Now suppose R is an equivelnce relation. We need to show that it's also circular. It is easy to do.

5. Ex. 7.2.6

Since every handshake is counted twice, the total sum must be even. (Or you can apply the handshake theorem).

6. Ex. 7.4.8

Clearly, no even length paths can exist. For odd length paths we have a choice of 3 vertices at every but the very last segment.
  1. n=2 Answer: 0
  2. n=3 Answer: 3^2
  3. n=4 Answer: 0
  4. n=5 Answer: 3^4

Ex. 7.5.36

  1. Kn each vertex has degree(n-1), so Kn has a Eauler circuit when n is odd.
  2. Cn each vertex has degree 2 for n>=3, - there is a E. circuit.
  3. Wn each vertex except the central one has degree 3, so there can be no E. circuit.
  4. Qn each vertex has degree n, so n must be even for a E. circuit to exist.