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:
