Math 137A Assignment 1

1. Draw the graph whose vertices are all ternary sequences of length 2 (i.e., ordered pairs where each entry is 0, 1, or 2.) and where two vertices are adjacent if they differ in exactly one entry. Draw this in such a way that all edges are straight line segments. Make the graph as aesthetically pleasing as you can!

2. Recall that a graph is k-regular if every vertex has degree k. A cubic graph is another name for a 3-regular graph.

(a) Draw two different (non-isomorphic) simple cubic graphs on 6 vertices.

(b) Draw all simple cubic graphs on 7 vertices.

(c) Draw all simple cubic disconnected graphs with 8 vertices. Ex-plain why your list is complete.

(d) Let n > 2. Find a construction that takes a simple cubic graphon 2n vertices and modifies it somehow to produce a new simplecubic graph on 2n+ 2 vertices.

3. Prove that the two drawings below are really the same graph. More precisely, find labelings of both graphs with labels {1, 2, . . . , 7} such that ij is an edge in the left graph if and only if ij is an edge in the right graph.

4. For every n, show how to construct a simple graph with degree se-quence (n, n, n − 1, n − 1, . . . , 4, 4, 3, 3, 2, 2, 1, 1).

5. For all n ≥ 4,  show how to construct a simple graph on n vertices with degree sequence (n − 1, 3, 3, . . . , 3).

6. If we allow parallel edges and loops, prove that there is a graph with degree sequence (d1, d2, . . . , dn) if and only if di is even.

7. Show that any simple graph with more than one vertex must have at least two vertices with the same degree. Hint: If not, what is the degree sequence?

8. If (d1, d2, . . . , dn) is the degree sequence of a simple graph, then prove

for all 1 ≤ k ≤ n.