CPTS 553 Graph Theory Assignment 2 solution

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