CSS220_Module7_Homework.docx

CSS 220 Module 7 Homework

Graph theory worksheet:

1.

· What is the of the graph?
· What is the degree of vertex N?
· What is the degree of vertex G?
· How many components does the graph have?

2. Let a graph have vertices D,E,F,G,H,I and edge set {{D,E},{D,F},{D,G},{D,H},{E,I},{H,I}}.
a. Draw the graph.
b. What is the degree of vertex G?
c. What is the degree of vertex D?
d. How many components does the graph have?

3. Which of the following degree sequences are possible for a simple graph? 
a. (5,3,3,3,2,2)
b. (9,8,8,7,4,4,4,2,2,1)
c. (8,6,3,3,2,2,2,1)
d. (6,5,4,4,3,3,3)

4. You are a mail deliverer. Consider a graph where the streets are the edges and the intersections are the vertices. You want to deliver mail along each street exactly once without repeating any edges. Would this path be represented by a Euler circuit or a Hamiltonian circuit?

5. A telephone company employee needs to check the telephone lines hanging from telephone poles for a cut in the line over a grid of streets in a city without service. Would the path taken on a graph representing the situation be an Euler circuit or a Hamiltonian circuit?

6. Construct a simple graph with vertices C, D, E, F, G, H whose degrees are 2, 2, 2, 0, 2, 2. What is the edge set? Draw the graph.

7. Which of the following graphs are connected? 
a.

b.

c.

d.

8. How many k-cliques are there in K_n?

9. Check the graph below for any of the following: Euler path, Euler circuit, Hamiltonian path, Hamiltonian circuit. Do any apply, if so list them.

10. Check the graph below for any of the following: Euler path, Euler circuit, Hamiltonian path, Hamiltonian circuit. Do any apply, if so list them.