Starting from:

$25

CS453 - Graph Theory  - Assignment 2  - Solved

1.     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  ๐‘ = ๐‘‘. 

 

A.     Sketch ๐บ; you are allowed to do this by hand and then copy your sketch electronically into your PDF submission. 

B.     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: 

 

A.     In terms of ๐‘Ÿ and ๐‘ , find a formula for the number of vertices of the grid graph ๐‘ƒ๐‘Ÿ,๐‘ . 

B.     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.   

A.     Show that there exists no cubic graph with an odd number of vertices. 

B.     For every integer ๐‘› โ‰ฅ 3, show that there exists a simple cubic graph (no loops, no parallel edges) with 2๐‘› vertices.  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. 

 

 

 

More products