Math 316/416

Problem Set 1

  1. 1.4 #13; add (c) Must the complement of a disconnected graph be connected? Prove it or give a counterexample.
  2. Show that every graph has two vertices with the same degree. [416 only: With a careful analysis, find all graphs with exactly one pair of vertices with the same degree.]
  3. Determine whether the following two graphs are isomorphic. Prove it.

    Pictures of Graphs

  4. Find all nonisomorphic graphs with four vertices, proving that they are all nonisomorphic and that you have found all of them.