Test #1

 

CSC126 October 8, 2008

 

 

Name ___KEY_____________________

      

1. Can there be a simple graph with 10 vertices each of degree 8?

                                                              YES        NO

 

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

          00101, 11101, 10001, 10111, 10100

 

(3-7) Are these graphs bipartite?

Graph A

3. Graph A.                                                              YES        NO  

 

Graph B

4. Graph B.                                                        YES        NO

 

5. Graph K2.                                                      YES        NO

 

 

6. Graph W12.                                                    YES        NO  

 

7. Graph Q117.                                                   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-21) Give the adjacency matrix for the indicated graphs.

18-19. Kn

 

 

 

 

 

 

 

 

 

 

 

 

 

 

20-21. Cn

 

 

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

 

22-23. 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      1           e         3

 

        b      4           f          6

 

        c       5           g         8

 

        d      7          h          2          

 

24-25. 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                      f      

        b                      g     

        c                       h     

        d                      i      

        e                      j      

                                k     

 

 

Graph E

 

 

Graph F

 

Graph G

 

 

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

E, not F, not G

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

Not E (circuit), not F, G

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

E, not F, not G

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

Not E (circuit), not F, G

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

E::a.b.c.e.f.g.b.f.c.d.e.g.h.a

 

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

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

 

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

E::a.b.c.d.e.f.g.h.a

 

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

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

 

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

34. Cn  all values

 

35. Q When n is even

 

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

36. Kn  when n is odd & n=2

 

37. W None

 

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

38. Cn All n

 

39. Wn    All n

 

40. For which values of m and n does Km,n have a Hamilton path, but not a circuit?

    K1,1 & all m ≥ 2 such that m=n 1

 

Graph H

 

 

41. How many cut vertices does the graph H above have?

3 c, d, e

 

42. How many cut edges does the graph H above have?

3 c-d, e-d, e-f

 

Graph I

 

  

Graph J

 

 

 

43. Which of the Graphs I & J is planar?

 

Graph J is planar.

 

44. Redraw it so that no edges cross.

 

Graph J Redrawn

 

 

 

 

Graph K

 

 

Graph L

 

 

 

45. What is the chromatic number of Graph K?

3

 

 

46. What is the chromatic number of Graph L?

2

 

(47-48) What is the chromatic number of:

47. Cn

2, if n is even

3, if n is odd

 

48. Km,n

2

 

Graph M

 

 

 

49-50. Find the least cost path from a to k.

a.c.g.j.k = 14

 

51. Suppose that a connected planar graph has 30 edges.  If a planar representation of this graph divides the plane into 20 regions, how many vertices does this graph have?

20 = 30 v + 2

V = 10 + 2 = 12

 

52. If G is a graph with 8 vertices and G is self-complementary, give one possible degree sequence for its vertices.

4.4.4.4.3.3.3.3

  

53. Draw all nonisomorphic simple graphs with 3 verices.

  

54. Draw all nonisomorphic simple graphs with 5 vertices and 3 edges.

  

 

                2-1-1-1-1                            2-2-1-1-0     

 

                  2-2-2-0-0                          3-1-1-1-0

 

55. For which of these nonplanar graphs , K6, K3,3, K3,4   can you remove any vertex along with incident edges to get a planar graph?

  

a. K5 a K4 removal of any vertex yields K4 which is planar. Yes

  

b. K6 a K5 removal of any vertex yields K5 which is not planar. No

  

c. K3,3 a K3,2 removal of any vertex yields K3.2 which is planar. YES

  

d. K3,4 a K2,4 removal of a vertex can yield K2,4 which is planar.

    K3,4 a K3,3 removal of a vertex can yield K3,3 which is not planar.

Therefore, since we cannot remove any vertex, answer is No.

 

56. Suppose the graph G has k connected components, e edges, v  vertices and is divided into r  regions by a planar representation.  Give a formula for the number of regions r  in terms of e, v and k.

r = e v + k + 1

 

57. Construct and display a Hamilton circuit for the graph Q3.

1213121

000-100-110-010-011-111-101-001-000

 

58-60. Prove by induction: Every connected graph, G, with n vertices has at least n-1 edges.

    

Proof (by induction on n):

  

Base Case:

Let G have 1 vertex.  Then G has no edges, i.e., e = 0.  So, e = n 1.

  

Inductive Step:

Assume that " n k, e n 1.  In particular, if n = k, then e k 1.

Now we must prove that if n = k + 1, e n 1.

  

Proof:

Let G′ = G with any vertex removed.

Then |V′| =  n 1 = k.

So, by the assumption, e′ k 1 = (n 1) 1.

That is e′ n 2.

Also, since G is connected, removing one vertex necessitates removing at least one edge.  In other words, e e′ + 1   (n 2) + 1 = n 1.

Thus, we have e n 1.

 

Extra Credit

 

EC-1. Draw a self-complementary graph with 8 vertices.  Show that it is isomorphic to its complement.

1,2,3,3,4,4,5,6 {unfinished}

  

EC-2. 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

 

 

EC-3. Draw all nonisomorphic simple graphs with 4 vertices.

 

a.     n = 4 Answer = 11 {Note: degree sequences given}

      0-0-0-0           1-1-0-0            2-1-1-0               3-1-1-0

 

      1-1-1-1             2-2-1-1           2-2-2-0                     2-2-2-2

 

                  3-3-2-2             3-2-2-1          3-3-3-3