Description
- 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.
- 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 𝐾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?
- Recall that a graph 𝐺 is said to be cubic if it is 3-regular, i.e., every vertex has degree 3.
- Explain why a loopless cubic graph must have an even number of vertices.
- For each integer 𝑛 ≥ 1, construct a loopless cubic graph with 2𝑛
- For each integer 𝑛 ≥ 3, construct a simple cubic graph with 2𝑛 (You could apply question #2 to this purpose.)
- Determine, with justification, whether the Petersen graph (drawn below, with vertex set 𝑉 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔, ℎ, 𝑖, 𝑗}) is bipartite:
CPTS 553: Graph Theory Assignment
