Description
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
b
c
d
e
f
g
h
i
j