Problem Set: Graph Theory
In this problem set we investigate some concepts in graph theory. The problems are of varying
difficulty; not all will be equally weighted in the grading.
Problem 0. Properties of Graphs.
Use the Lab page Graph Properties to learn or to remind yourself of the definitions of the diameter of a graph, of complete, cycle, grid, path, star and wheel graphs, and of the conditions
under which a graph is connected, regular, planar and/or bipartite. When you want to return to
this page, use the Back option of your browser, not the Previous button given on Graph Properties.
The list below gives a number of true statements (Facts; these you don’t have to prove), and
asks some questions. Please answer each question.
Fact 1: All complete graphs, cycle graphs, grid graphs, path graphs, star graphs and wheel graphs
Fact 2: All cycle graphs, grid graphs, path graphs, star graphs and wheel graphs are planar.
Question: Is a complete graph Kn ever planar? If yes, for what n is Kn planar?
Fact 3: All complete graphs and cycle graphs are regular, but only two star graphs, and only one
wheel graph, are regular.
Question: Can you identify these special wheel graphs and star graphs? Which grid graphs
1Fact 4: The diameter of a complete graph is always 1.
Question: What is the diameter of a path graph Pn? And that of a cycle graph Cn? Or a
grid graph Gm,n? The answer should be given in terms of any n and m.
Question: Show that the diameter of a star graph Sn for n > 2 or a wheel graph Wn for n > 4 is
Fact 5: All grid graphs, path graphs, and star graphs are bipartite.
Question: Can you identify the two special sets of vertices in each of these cases?
2Question: Which cycle graphs are bipartite? And which complete graphs? Wheel graphs?
Problem 1. Directed and Undirected Graphs.
Draw a directed graph G, and label two vertices x and y in such a way that the distance from
x to y is 7 in the directed graph G, but so that the distance from x to y would be 2 if we made an
undirected graph H by erasing directions on the edges of G.
Problem 2. Sum of Degrees.
a) Draw three small graphs (4-10 edges each) and, for each vertex, write the degree next to the
3b) For each of the three graphs in part (a), add up the degrees of the vertices in that graph.
Note that the sum for each graph is even.
c) Explain why for any graph, the sum of the degrees of the vertices is always even.
Problem 3. Trees.
a) Draw three small (8-15 vertices) trees.
4b) For each of the three trees in part (a), count the number of vertices, V , and the number of
edges, E. Note that V − E = 1 for each tree.
c) Explain why for any tree, V − E must always equal 1.
5Problem 4. The Chinese Postman Problem.
In class, we briefly touched on a simplified version of the Chinese Postman Problem, a close cousin
of the Koenigsberg bridge problem that was studied by the Chinese mathematician Meigu Guan in
the 1960s. We will now explore the original Chinese Postman Problem.
On his first day on the job, a new postman is given the map below and instructed that he must
deliver letters to houses along each of the streets on the map. The postman wants to find the
shortest possible route that includes each of the streets on the map at least once and returns him
to his starting point at the post office (the intersection in the upper lefthand corner).
a) Draw the graph corresponding to the given map. Vertices in your graph will represent intersections and edges will represent the streets that connect pairs of intersections.
6b) Add a weight to each edge (in the graph you drew above) to represent the length of the corresponding street.
c) Since the postman must travel each street at least once and return to his starting point, an
Eulerian cycle, if it exists, will be the shortest possible route. Is it possible to find such a
cycle for this graph? Use the result of Euler discussed in class to explain why or why not.
d) Add a new edge parallel to an existing edge (that is, connecting the same two vertices as an
existing edge) in such a way that you make an Eulerian cycle possible. Verify that you can
now find an Eulerian cycle in the graph.
7e) How would the postman actually travel the route represented by your Eulerian cycle? In
particular, since the postman can’t build new streets, how does he travel your new edge?
f) In view of your answer to (e), what should the weight of your new edge be?
g) Find the total distance the postman needs to travel to complete the route represented by your
new Eulerian cycle. Is this route the shortest route that satisfies the postman’s constraints?
If yes, explain why. If not, find a shorter route.
8h) Now consider the following example:
How many ways are there to add 2 parallel edges to this graph so as to make an Eulerian
cycle possible? Which way creates the shortest possible Eulerian cycle?
i) Using what you’ve learned, explain how in general a postman can find the shortest route that
includes each street at least once and ends at his starting point.
These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction
of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice.
Unethical use is strictly forbidden.