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