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