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:

1. • ≠ and = , or

   • = and is an edge of

Later on, we will call this graph ₂ × . As an example, if is ₄, 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.

3. 1. Explain why a loopless cubic graph must have an even number of vertices.

3. 2. For each integer ≥ 1, construct a loopless cubic graph with 2 vertices.

3. 3. For each integer ≥ 3, construct a simple cubic graph with 2 vertices. (You could apply question #2 to this purpose.)

3. Determine, with justification, whether the Petersen graph (drawn below, with vertex set = { , , , , , , , ℎ, , }) is bipartite:

a

	f
e	b
j
	g

i ^h

c

d