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:
