[SOLVED] CS453 - Assignment 2

Description

Among all simple graphs (no loops, no parallel edges) with 𝑛 = 100 vertices, determine (with justification) the minimum possible and the maximum possible values for 𝑚, the number of edges such a graph could have.

2. Let 𝐺 be the simple graph with vertex set

𝑉 = {00, 01,02, 10,11, 12, 20,21, 22};  |𝑉| = 9

and where vertices 𝑎𝑏 and 𝑐𝑑 are joined by an edge when exactly one of the following conditions holds (so there are no loops):

𝑎 = 𝑐  or  𝑏 = 𝑑.

1. Sketch 𝐺; you are allowed to do this by hand and then copy your sketch electronically into your PDF .
2. Determine 𝑚, the number of edges of 𝐺.

3. The “grid graph” 𝑃_𝑟,𝑠 is the cartesian product of the two paths 𝑃_𝑟 and 𝑃_𝑠. For instance, 𝑃_3,4 is drawn below:
   1. In terms of 𝑟 and 𝑠, find a formula for the number of vertices of the grid graph 𝑃_𝑟,𝑠.
   2. In terms of 𝑟 and 𝑠, find a formula for the number of edges of the grid graph 𝑃_𝑟,𝑠.

4. Recall that a graph 𝐺 is “cubic” if and only if it is 3-regular.
   1. Show that there exists no cubic graph with an odd number of vertices.
   2. For every integer 𝑛 ≥ 3, show that there exists a simple cubic graph (no loops, no parallel edges) with 2𝑛 One way to do this is to produce a construction, i.e., give a set of 2𝑛 vertices and a recipe for when vertices are joined by edges for constructing such graphs.