Test #1

 

CIS126 March 5, 2008

 

 

Name ___KEY_____________________

      

1. Can there be a simple graph with 7 vertices each of degree 4?

                                                              YES        NO

 

2.List all the vertices that vertex 10011 of Q 5 is connected to.

          00011, 11011, 10111, 10001, 10010

 

(3-7) Are these graphs bipartite?

Graph A

3. Graph A.                                                              YES        NO

 

Graph B

4. Graph B.                                                       YES        NO  

 

5. Graph K5.                                                      YES        NO  

 

6. Graph C12.                                                     YES        NO

 

7. Graph Q21.                                                     YES        NO

 

8-17. Fill in the chart below to show how many vertices (#V) and how many edges (#E) each type of graph has.

 

Kn                         Cn                         Wn                       Km,n                   Qn

 

#V   n            n            n+1               m+n              2n

 

#E   n(n-1)/2  n            2n          mn         n*2n /2

 

18. Which of the graph s Kn, Cn, Wn and Qn   are regular for all values of n?

Kn, Cn, and Qn

 

19. For what values of m & n is the graph Km,n regular?

Whenever m=n

 

(20-25) Give the adjacency matrix for the indicated graphs.

20-21. Kn

 


 

22-23. Km.n

 

 

24-25. Qn+1

 

 


 

(26-29) Are the indicated pairs of graphs isomorphic or not?  If they are, indicate a vertex pairing that would reveal the isomorphism.

 

26-27. Graph Pair: C-1 & C-2

Graph C-1                                  Graph C-2

 

Isomorphic?                                                  YES        NO  

 

    Vertex paring::

        C-1  C-2          C-1  C-2

        a                      f      

        b                      g     

        c                       h     

        d                      i      

        e                      j      

                                k     

 

28-29. Graph Pair: D-1 & D-2

Graph D-1                                  Graph D-2

 

Isomorphic?                                                  YES        NO

 

   Vertex paring::

        D-1  D-2     D-1     D-2

 

        a      1           e         2

 

        b      3           f          4

 

        c       5           g         6

 

        d      7          

 

Graph E

 

 

Graph F

 

Graph G

Graph D

 

 

30. Which of the graphs E through G have an Euler circuit?

None

31. Which of the graphs E through G have an Euler path (but not a circuit)?

G & F

32. Which of the graphs E through G have a Hamilton circuit?

F

33. Which of the graphs E through G have a Hamilton path (but not a circuit)?

G

34. For those which have an Euler circuit, give the circuit.

None

 

35. For those which have an Euler path (but not a circuit), give the path.

G:: g.a.b.g.c.b.f.c.d.f.e

 

F:: e.c.d.e.a.b.e.g.h.g.i.e.f.a.j.h.i.j.f.i

 

36. For those which have a Hamilton circuit, give the circuit.

F:: a.b.e.c.d.h.g.i.f.j.a

 

37. For those which have a Hamilton path (but not a circuit), give the path.

G:: d.c.g.a.b.f.e

 

(38-40) For which values of n do the following graphs have an Euler circuit?

38. Kn  when n is odd

 

39. W None

 

40. For which values of m and n does Km,n have an Euler circuit?

when m & n are both even

 

(41-43) For which values of n do the following graphs have an Euler path?

41. Kn  when n is odd & n=2

 

42. Q Even n & n=1

 

43. For which values of m and n does Km,n have an Euler path?

when m & n are both even; m odd & n=2; K1,1

 

(44-46) For which values of n do the following graphs have a Hamilton circuit?

44. Cn All n

 

45. Qn    All n ≥ 2 (but not n =1)

 

46. For which values of m and n does Km,n have a Hamilton circuit?

    All m,n ≥ 2 such that m=n

 

Graph H

 

 

 

47. For Graph H above, draw the search tree that would be produced to find the shortest path from vertex #1 to vertex #12.  When expanding, proceed left to right within each level.

  

Graph I

 

 

 

 

48. How many cut vertices does the graph I above have?

3 a, e, d

 

49. How many cut edges does the graph I above have?

2 a-b, e-f

  

Graph J

 

 

 

 

50. How many cut vertices does the graph J above have?

4 b, c, d, f

 

51. How many cut edges does the graph J above have?

4 a-b, c-f, d-f, d-e

 

52. For what values of n does the graph Wn have at least one cut vertex?

none

 

53. How many cut edges does the graph K1,2 have?

2

    

Graph K

 

 

 

 


 

Why Graph K is not planar: Start with a small number of vertices and add one vertex at a time, keeping the graph planar at every step.

Step 1: Start with the triangle b-e-f.  Add vertex d, as below.

 

 

Step 2: Add vertex a, placing it so that no edges cross.

 

Step 3: Add vertex g, placing it so that no edges cross.

Step 4: We try to add vertex c, placing it so that no edges cross.  But we cannot find a place.  To determine that this is impossible to do, we label the regions of the planar graph that we have, and try placing c in each of the regions.  We find that it is impossible, as shown below.

 

Analysis:

If we place vertex c in Region 1, then we cross an edge to reach vertices g & d.

"                      Region 2,                    "                               vertex g.

"                      Region 3,                    "                       vertices e & d.

"                      Region 4,                    "                               vertex e.

Therefore:

Graph K is not planar.

Graph L

 

 

 

54. Which of the Graphs K & L is planar?

 

Graph L is planar.

 

55. Redraw it so that no edges cross.

 

 

 

 

56. What is the chromatic number of Graph K?

3

 

 

57. What is the chromatic number of Graph L?

2

 

(58-0) What is the chromatic number of:

58. Kn

n

59. Wn

3, if n is even

4, if n is odd

 

60. Qn

2

 

Extra Credit

 

 

EC-1. If G is a self-complementary graph with 9 vertices, what is a possible degree sequence for G?

1,2,3,4,4,4,5,6,7

 

EC-2. If G is a self-complementary graph with 8 vertices, what is a possible degree sequence for G?  Draw the graph.

1,2,3,3,4,4,5,6

  

EC-3. What is the edge-chromatic number of K5?  If the vertices are labeled a, b, c, d & e in clockwise order, list the colors used and the edges of each color.

 

              a   b   c   d   e

    a   -   R   G   B   Y

    b   R   -   B   Y   G

    c   G   B   -   I   R

    d   B   Y   I   -   B

    e   Y   G   R   B   -

 

EC-4. Generate and display a Hamilton circuit for Q5.

1213121412131215121312141213121

121

 

00000-10000-11000-01000-01100-11100-10100-00100-00110-10110-11110-01110-01010-11010-10010-00010-00011-10011-11011-01011-01111-11111-10111-00111-00101-10101-11101-01101-01001-11001-10001-00001

In decimal: 0-16-24-8-12-28-20-4-6-22-30-14-10-26-18-2-3-19-27-11-15-31-23-7-5-21-29-13-9-25-17-1

 

EC-5. Let G = (V, E) be a simple graph with |V| = n.  Prove that the edge-chromatic number of G is n.

It is sufficient to show that the edge-chromatic number can never be > n.  The chart below shows that n colors are sufficient.  The colors are indicated by number.  The colors in braces indicate placeholders, locations that are not colored.

 

              v1  v2  v3  v4  v5  .   .   vn-2 vn-1 vn 

    v1  {1} 2   3   4   5   .   .   n-2 n-1 n

    v2  2   {3} 4   5   6   .   .   n-1 n   1

    v3  3   4   {5} 6   7   .   .   n   1   2

    v4  4   5   5   {7} 8   .   .   1   2   3

    v5  5   6   7   8   {9} .   .   2   3   4

    .

    .

    Vn-2 n-2 n-1 n   1   2   .   .   {n-5}n-4 n-3

    Vn-1 n-1 n   1   2   3   .   .   n-4 {n-3}n-2

    Vn  n   1   2   3   4   .   .   n-3 n-2 {n-1}

 

EC-6. Let G = (V, E) be a connected simple planar graph with |V| = 13.  If three of those vertices have degrees of 10, 6 and 6, respectively, what is the maximum number of edges G can have?  Does G have an Euler circuit (or path)?  Does G have a Hamilton circuit (or path)?

Maximum is 33.  G has neither Euler or path, but does have a Hamilton circuit & path.

 

EC-7. Let G = (V, E) be a connected simple planar graph with |V| = 13.  If three of those vertices have degrees of 10, 6 and 6, respectively, what is the minimum number of edges G can have?  Does G have an Euler circuit (or path)?  Does G have a Hamilton circuit (or path)?

Minimum is 19.  G has neither Euler circuit or path, nor a Hamilton circuit or path.