Description
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.