Math 11
mzlkha
WeeklySummary11b.docWeekly Summary, Week 7, Chapter 11/part b Name:
Due on Sunday, October 14, by midnight.
Type your answers under the questions given below, or, print out this sheet, use pen or pencil to fill it out, and email a scan or photo of it to the instructor.
1) Suppose that an extensive subway system has 34 stations, and that each station has tracks that directly connect it to 6 other stations. Can this system be built so that no track crosses over any other track? Prove your answer.
2) Which of the following three graphs contains a Hamilton cycle? If the answer is yes to any of them, then give the vertex ordering.
|
|
|
|
3) Is the following graph a planar graph?
4) Is the following graph a planar graph?
5) The following graph is non(planar. Prove this using Kuratowski's theorem (be very clear).
6) In the following graph each vertex represents a person. Each edge indicates an acquaintance. For example, m knows n, and x knows v, but o does not know e, and a does not know d. What is the largest number of people that are mutually unacquainted? Give a list of those people.
7) If you can find an independent set of vertices I in a graph G in such a way that:
e + 2 | I | (
å
Î
I
a
a
)
deg(
< v[e = total number of edges in G; v = total number of vertices in G;
å
Î
I
a
a
)
deg(
= sum of degrees of vertices in I.]Then the graph has no Hamilton cycle.
Find an independent set of vertices I in the following graph that makes the inequality true, thus showing that the graph has no Hamilton cycle. Fill out your answers below.
I = e = 2 | I | =
å
Î
I
a
a
)
deg(
= v =Be sure that your choice of I satisfies e + 2 | I | (
å
Î
I
a
a
)
deg(
< v
