April 27th

Graph Vocabulary Terms

The problem set

  1. Draw all possible graphs on three vertices. How many edges are there in each graph? What are the degree sequences? Can you do this on pseudographs?
  2. Draw \(K_7, K_{3,4}, K_{2,6}\).
  3. For each of these degree sequences either draw the graph or explain why no such graph exists:
  4. How many complete bipartite graphs are there with \(n\) vertices?
  5. Does there exist a graph with five vertices, every vertex incident with at least one edge, but no two edges adjacent? Explain.
  6. Is this graph bipartite?
  7. How about this one?
  8. * (next DC) Can you come up with a general method for this?
  9. Let \(G_0\) be the graph from problem 6. Draw \(G_0 \setminus {f}\). Draw \(G_0 \setminus {ab}\).

Follow up to the derangement video. (Since today is so literal.)