Saint Xavier University Module 7 Graph theory worksheet

CSS 220 Module 7 Homework
Graph theory worksheet:
1.
•
•
•
•
What is the order 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.