## 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