$24
1. Among all simple graphs with 21 vertices, determine (with justification) the minimum possible and the maximum possible number of edges such a graph could have.
2. Suppose is a simple graph (no loops, no parallel edges) with vertices and edges. Let be the simple graph whose vertices take the form (0, ) or (1, ) for each vertex of . Two vertices ( , ) and ( , ) of are adjacent if either of the following two conditions holds:
◦ ≠ and = , or
◦ = and is an edge of
Later on, we will call this graph 2 × . As an example, if is 4, then is drawn below:
In terms of and , how many vertices does have and how many edges does have?
3. Recall that a graph is said to be cubic if it is 3-regular, i.e., every vertex has degree 3.
a. Explain why a loopless cubic graph must have an even number of vertices.
b. For each integer ≥ 1, construct a loopless cubic graph with 2 vertices.
c. For each integer ≥ 3, construct a simple cubic graph with 2 vertices. (You could apply question #2 to this purpose.)
4. Determine, with justification, whether the Petersen graph (drawn below, with vertex set = { , , , , , , , ℎ, , }) is bipartite:
a
f
e
b
j
g
i h
c
d