[SOLVED] CPTS553-Assignment 2

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 𝑚 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 𝐾₂ × 𝐺.  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.
   1. Explain why a loopless cubic graph must have an even number of vertices.
   2. For each integer 𝑛 ≥ 1, construct a loopless cubic graph with 2𝑛
   3. For each integer 𝑛 ≥ 3, construct a simple cubic graph with 2𝑛 (You could apply question #2 to this purpose.)

4. Determine, with justification, whether the Petersen graph (drawn below, with vertex set 𝑉 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔, ℎ, 𝑖, 𝑗}) is bipartite:

CPTS 553: Graph Theory Assignment