$25
1. Among all simple graphs (no loops, no parallel edges) with ๐ = 100 vertices, determine (with justification) the minimum possible and the maximum possible values for ๐, the number of edges such a graph could have.
2. Let ๐บ be the simple graph with vertex set
๐ = {00, 01,02, 10,11, 12, 20,21, 22}; |๐| = 9
and where vertices ๐๐ and ๐๐ are joined by an edge when exactly one of the following conditions holds (so there are no loops):
๐ = ๐ or ๐ = ๐.
A. Sketch ๐บ; you are allowed to do this by hand and then copy your sketch electronically into your PDF submission.
B. Determine ๐, the number of edges of ๐บ.
3. The โgrid graphโ ๐๐,๐ is the cartesian product of the two paths ๐๐ and ๐๐ . For instance, ๐3,4 is drawn below:
A. In terms of ๐ and ๐ , find a formula for the number of vertices of the grid graph ๐๐,๐ .
B. In terms of ๐ and ๐ , find a formula for the number of edges of the grid graph ๐๐,๐ .
4. Recall that a graph ๐บ is โcubicโ if and only if it is 3-regular.
A. Show that there exists no cubic graph with an odd number of vertices.
B. For every integer ๐ โฅ 3, show that there exists a simple cubic graph (no loops, no parallel edges) with 2๐ vertices. One way to do this is to produce a construction, i.e., give a set of 2๐ vertices and a recipe for when vertices are joined by edges for constructing such graphs.