Starting from:
$30

$24

Graph Theory Assignment 2 Solution

    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:

        ◦ ≠  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?

    3. Recall that a graph is said to be cubic if it is 3-regular, i.e., every vertex has degree 3.

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

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

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


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



a




f
e
b
j


g





i    h


c
d

More products