Problem 1. Maximize the Flow.

The Ford-Fulkerson algorithm is another name for the process of repeatedly finding augmenting paths and upping the flow by one unit along them that we saw in class. In this problem, we will use an online java applet http://www.cs.pitt.edu/~kirk/cs1501/animations/Network.html to get some practice with the Ford-Fulkerson algorithm.

a) Create a directed graph of at least 8 vertices and at least 12 edges of at least 5 different capacities. Make sure you designate a source vertex and a destination (target) vertex. Draw your graph in the space below and then use the online java applet to draw it. You will first need to use the add node command to place your vertices. Then you will use the add edge command and click on ordered pairs of vertices to add edges. Finally, adjust the capacity on each edge by adjusting the number under capacity on the side and then clicking the appropriate edge. Don?t forget to use the source and destination buttons to identify the source vertex and destination vertex.

Answers will vary. One possible graph with resulting answers follows.

b) Hit the step button once. This will find one augmenting path and increase the flow along it. Either print the result or draw the graph and label it with the resulting flow.

After running the algorithm one step, the resulting graph is:

c) Keep running the algorithm on the applet until no additional augmenting paths can be found. Either print and attach the result or draw the graph and label it with the resulting flow.

The final graph with a maximum feasible flow indicated is:

d) Find the min cut of the graph that prevents the algorithm from finding any more augmenting paths.

Finally, the following figure shows the partition between the source and target groups that forms the min cut. We can verify that it is in fact the min cut by noting that all three of the forward-pointing edges involved in this cut are filled to capacity in the max flow above in part (c).

Problem 2. Street Network

The following directed graph represents the road network between a city and a suburb of that city:

Each morning, most of the people in the suburb are trying to commute to their workplaces in the city, so we would like to be able to move as much flow as possible from the suburb (the source) to the city (the destination).

a) Find the min cut for this graph. Highlight or otherwise indicate the edges that go from the source's group of vertices to the target's group of vertices in the min cut. What is the capacity of this cut? What is the maximum feasible flow for this network?

Capacity = Max feasible flow = 6+4+5+3 = 18.

b) Suppose you are given the job of building a new road to shorten everyone?s morning commute. The road can have a capacity of up to three and can connect any two vertices. Where would you place this road? What is the new min cut? What is the maximum feasible flow of the new graph?

Answer:

Since we are given a road of capacity 3, we hope to place it in order to raise the capacity of the entire network by 3. Currently, this capacity is limited by the capacity of the min cut, so we must place this edge so that it crosses the min cut. More specifically, it must start in the source group and end in the target group. One way of doing this is shown below:

We can verify that we have the same min cut as before, but now there is one more edge going from the source group to the target group in the min cut, so the new capacity of the network is:<./p>

Capacity = 6 + 4+ 5 + 3 + 3 = 21

Since the maximum feasible flow of a graph is always equal to the capacity of the min cut, we also have:

Maximum feasible flow = 21.

c) Explain why traffic in cities often backs up at bridges in terms of the max flow, min cut theorem (Thm 3 in the first week's notes).

You and your friends Amy, Ben, Christine, Dan, and Emily are going to the movies. You want to take the least number of cars possible, but Ben refuses to be in the same car with any of your female friends and Dan refuses to be in the same car with Ben or Emily.

a) Draw a graph describing the conflicts.

b) What does the greedy coloring theorem allow you to say about the minimum number of cars you can take?

c) What is the actual minimum number of cars you can take? Please give an actual assignment of people to cars that resolves the conflicts for this minimum number of cars and explain what prevents you from taking one fewer car than this minimum.

In fact, we may color this graph with three colors:

The coloring above shows that we may take 3 cars to the movies: a ?red? car containing Amy, Christine, and Emily, a ?blue? car containing Dan and me, and a ?green? car containing Ben. Can we perhaps color this graph with one fewer color and thus take one fewer car to the movies? We see that we cannot because of the triangle formed by Ben, Dan, and Emily; if we try to color with 2 colors, we will be forced to give two of these three the same color, and an edge in the triangle will have both endpoints the same color. Thus, we conclude that the minimum number of cars we can take to the movies is three.

Problem 4. Coloring Trees

All trees are planar graphs, so Appel and Haken's celebrated result tells us that they can be colored properly with four or fewer colors.

We think we can do better. Can all trees be colored with three or fewer colors? Can all trees be colored with two or fewer colors? Give a general procedure that colors a tree with the minimum number of colors, and explain why your procedure works.

Draw a small tree (10-20 vertices) and demonstrate your procedure with that tree.

Suppose we have a tree that we wish to color. We first pick a vertex to use as a root and draw the tree in the cascading form shown below. This can always be done for any tree. We notice that the tree now has layers: the top layer is our initial vertex, the next layer is all vertices adjacent to (distance 1 from) our initial vertex, the next layer is all those at distance 2 from our initial vertex, and so forth. Since we have a tree, each vertex is only adjacent to vertices in the layer above it and vertices in the layer below it. There are no other connections.

Thus, we may color the layers in alternating colors, giving the initial vertex the color 1, the next layer color 2, the following layer color 1 again and so forth. Since each vertex is only adjacent to vertices in the layers immediately above and below it (which are colored the opposite color from its layer), no two adjacent vertices get the same color. Hence, we have a proper coloring of our tree.

Problem 5. Complete Graphs

The complete graph on N vertices, denoted by K_N, is a graph with N vertices in which each pair of vertices is joined by an edge. We do not have multiple edges between the same pair of vertices, nor do we have loops in K_N.

Some of the graphs K₁, K₂, K₃, K₄, K₅, K₆, and K₇ can be drawn in a plane without any edges crossing over each other, and some will always have at least one edge crossing over another no matter how we try to draw them. Which of these seven graphs can be drawn without edges crossing (recall that you can draw edges curved), and which of the graphs cannot be drawn without edges crossing? If you say that a graph can be drawn without edges crossing, furnish such a drawing to prove your claim. If you say that a graph cannot be drawn without edges crossing, you need to prove that it cannot be done, no matter how you try to do it. Since there are infinitely many ways to try to draw a graph, you cannot justify your claim by simply saying that you tried but did not succeed. Rather, you need to provide a justification. Hint: use Appel and Haken's result that all planar graphs are 4-colorable.

K₁, K₂, K₃, and K₄ can all be drawn in the plane:

However, K₅, K₆, and K₇ cannot be drawn in a plane. We will first show this for K₅. Suppose that we colored K₅ with 4 colors. Then, two vertices of K₅ would have to have the same color, but since every pair of vertices in K₅ is connected by an edge, we know that this is not a proper coloring of K₅. Hence, K₅ can not be 4-colorable. However, the result of Appel and Haken tells us that every planar graph is 4-colorable, so since K₅ is not 4-colorable, it cannot be a planar graph.

By the same reasoning, neither K₆ nor K₇ is 4-colorable. Hence, neither of these graphs can be a planar graph.

Problem 6. Coloring Polygons

Suppose that N is an integer greater than 1. What is the chromatic number of a polygon with N sides? Does your answer depend on N?

The chromatic number of an N-sided polygon is 2 if N is even and 3 if N is odd. To show this, take an N-sided polygon and number its vertices in order v₁ through v_N so that for every k from 2 to N-1, v_k is adjacent only to v_k-1 and v_k+1 and v_N is adjacent to v_N-1 and v₁. Color this polygon by giving all the vertices with odd indices (v₁, v₃, v₅, etc.) color 1 and all vertices with even indices (v₂, v₄, v₆, etc.) color 2.

If N is even, then there will be no conflicts created by this coloring since every vertex with an even index is adjacent to two vertices with odd indices and vice versa. In particular, v_N, which has color 2, is adjacent to v_N-1 and v₁, both of which are color 1.

If N is odd however, we do have a conflict. When we get to v_N, we find that v_N-1 has color 2 since N-1 is even, but v₁ has color 1 since 1 is odd. Hence, since v_N is adjacent to both a vertex of color 1 and a vertex of color 2 already, we must introduce a third color in order to color it.

We might wonder if we could have somehow reassigned colors to the other N-1 vertices so as to avoid this conflict. However, once we choose a color for v₁, we find that we are forced into each of our other color selections: we must color each vertex with the opposite color of the one it is adjacent to. Hence, we cannot resolve the conflict at v_N without introducing a conflict earlier down the line.

Problem 7. 2-Colorable Graphs

Recall that we always assume that our graphs are connected unless explicitly noted otherwise. All graphs in this problem are assumed to be connected.

(a) First warm up: Which (connected) graphs are 1-colorable? Can you classify them all?

Second warm up: By an odd polygon, we mean a polygon with an odd number of sides. Show that a graph containing an odd polygon is not 2-colorable. (Hint: See the previous problem.)

Warm-up 1: The only 1-colorable (connected) graph is a single vertex:

If we have even a single edge in the graph, then we will need two different colors for its endpoints. If we have more than one vertex without any edges, then the graph is not connected.

Warm-up 2: As was shown in the previous problem, no odd polygon is 2-colorable (we won?t repeat the justification here). Hence, if we have a graph that contains an odd polygon, then there is no way of coloring those vertices involved in the odd polygon with 2 colors, so the graph as a whole cannot be 2-colorable. Thus, we see that no graph containing an odd polygon can be 2-colorable.

(b) Draw a graph (with 10-12 vertices) that is not a tree and has no odd polygons. Color one vertex blue. Now color the rest of the vertices properly using only blue and red. You should find that you are able to do this, but that there is only one way to do this (i.e., each vertex has a color assignment forced upon it after you color the first vertex blue). Is there a succinct rule that which tells you what color a vertex must receive?

Procedure: Choose a vertex to begin with. Color this vertex color 1. Now color all vertices an odd distance from this vertex color 2 and all vertices an even distance from this vertex color 1.

Demonstration of procedure

(c) Come up with a general procedure for coloring graphs without odd polygons. Your procedure should always properly 2-color such a graph. You should explain why your procedure never fails to work.

Suppose that when we use our procedure above, we don?t get a proper coloring. That is, suppose that two adjacent vertices (let?s call them x and y) are given the same color by our procedure. Then, x and y are either both at an odd distance or both an even distance from the initial vertex. In either case, there is then a path from x to y by way of the initial vertex that is of even length.

Moreover, if this path visits the same vertex more than once, (i.e. there was a common vertex v on the paths from x and y to the initial vertex), then we may remove the (even length) round trip between v and the initial vertex from our path in order to obtain an even length path from x to y with no repeated vertices. Hence, there must exist an even length path from x to y with no repeated vertices in the graph.

But x and y are adjacent, so there is also a path of length 1 (a single edge) from x to y. Combining this edge with the even length path found above, we find that there is a circuit with no repeated vertices whose total length is odd. In other words, we have found an odd polygon in the graph.

Hence, we have shown that if our procedure doesn?t work for some graph, then that graph must contain an odd polygon. So conversely, if a graph contains no odd polygons, then our procedure will always work for that graph.

Problem 8. Plato and Euler

4) It is an interesting fact that any graph that represents the corners and edges of a simply-connected three-dimensional solid can be drawn as a planar graph. The resulting planar graph is called a planar embedding of the solid.

So, for example, we can find a planar embedding for the tetrahedron by taking the base of the pyramid and stretching it out until we can fit the other three edges inside:

Note that the resulting two-dimensional graph is isomorphic to the graph in three dimensions.

a) Draw a planar embedding of a cube.

The pyramid and the cube each have some interesting features. Each face is the same regular polygon (one in which all sides and angles are the same) and the number of these faces that meet, as well as the angles at which they meet, are the same at each vertex. For example, each face of the pyramid is an equilateral triangle and exactly three such faces meet at each of the four vertices.

It can be shown using the Euler characteristic (see Challenge Problem #3) that there are only five solids with these properties. The remaining three are:

The octahedron, a solid with 8 triangular faces, four of which meet at each vertex:
The dodecahedron, a solid with 12 pentagonal (5-sided) faces, three of which meet at each vertex, can be viewed at MathWorld, and here is the graph:
The icosahedron, a solid with 20 triangular faces, five of which meet at each vertex, can be viewed at MathWorld, and here is the graph:

Knowledge of the platonic solids goes back thousands of years to the ancient Greeks. Plato proposed that four of these five solids were associated with the four elements: fire, earth, air, and water. Moreover, much in the same way that we believe today that all matter is made from the basic chemical elements in the form of tiny atoms, he believed that all matter was made of these four elements in the form of tiny platonic solids. Aristotle introduced the idea of a fifth element, aether, which was associated with the dodecahedron by Philolaus. We should note that modern chemistry shows that many chemical compounds have molecules with tetrahedral and octahedral shapes.

b) Find the chromatic number of each platonic solid. For each solid, provide a coloring of the associated graph that uses exactly this many colors and briefly explain why you can?t use fewer colors.

Tetrahedron:

As shown, we may color the tetrahedron with 4 colors. However, we may not use fewer than 4 colors since each of the tetrahedron?s four vertices is adjacent to all other vertices, meaning that we cannot give any two of the four vertices the same color or we will have a conflict. Thus, the chromatic number of the tetrahedron is 4.

Cube:

A coloring of the cube using 2 colors is shown. It is not possible to use 1 since the graph contains edges. Thus, the chromatic number of the cube is 2.

Octahedron:

We may color the octahedron with 3 colors as shown. It is not possible to use two colors since this graph contains odd polygons (triangles) (see problem 7). Hence, the chromatic number of the octahedron is 3.

Dodecahedron:

A coloring of the dodecahedron using 3 colors is shown. We may not use fewer than three colors since this graph too contains odd polygons (pentagons). Thus, the chromatic number of the dodecahedron is 3.

Icosahedron:

As shown, we may color the icosahedron with 4 colors. However, it is a bit tricky to justify why we can?t use fewer that 4. Clearly, fewer than 3 is not possible since the graph contains triangles, but why can?t we get away with using 3 colors instead of 4? One possible justification for this is that the graph contains the following structure:

The outer ring of this structure is an odd polygon, so we must use at least 3 colors to color it. Then, we find that the innermost vertex is adjacent to each of the five vertices of this polygon, so it cannot take any of these three colors, and we must therefore use a fourth color to color it.

c) Count the number of vertices, edges, and faces for each platonic solid and show that each one satisfies the Euler characteristic. (Don't forget to count the unbounded face if you choose to count faces using the planar embeddings.)

d) Could we have a Platonic solid with 18 seven-sided faces and 30 vertices? How about one with 18 five-sided faces and 30 vertices? (Hint: Since each edge is where two faces meet and each face has five sides, how many edges are there in the graph for this solid?)

Neither can be a Platonic solid.

18 7-sided faces: If a solid has 18 7-sided faces and 30 vertices, then it is not possible for the same number of faces to meet at every vertex since 30 does not divide 18*7 = 126 evenly.

18 5-sided faces: If a solid has 18 5-sided faces, then the faces have a total of 18*5 = 90 sides between them. When we put all these faces together into a solid, we will get an edge everywhere that two sides of different faces meet, so we will have a total of 90/2 = 45 edges in our solid. However, this means that V-E+F = 30-45+18 = 3, so the Euler characteristic is not satisfied. Thus, such a solid cannot exist.

e) Will all solids satisfy the Euler characteristic? Explain why or why not.

As was noted earlier in the problem, all solids can be drawn as planar graphs. Hence, since the Euler characteristic holds for all planar graphs, it holds for all solids.

Problem 9. Disconnected Countries

In our original map-coloring problem, we assumed that every country is a connected mass of land, and we wanted to color adjacent countries with different colors. (Countries that only touch corner-to-corner were not counted as adjacent.)

Now we look at the map-coloring problem that is in all respects the same, except that now we allow the possibility that a country is made up of multiple disconnected masses of land. We insist that all the various patches that make up a country be colored the same color in our coloring. As usual, when two territories belonging to different countries are adjacent (not counting corner-to-corner touching as adjacency), we insist that they receive different colors.

Do six colors suffice to color every map in this more general situation? If so, explain why. If not, then furnish a map that is not 6-colorable, and make sure you name your countries (single-letter names will suffice) and label each territory with the letter of the country to which it belongs.

No, in a map with disconnected countries, the six-color theorem does not necessarily have to hold. For example, consider the following map:

In this map, there are 7 countries (A, B, C, D, E, F, and G). Furthermore, every country is adjacent to every other country, so if we gave two of the seven countries the same color, then two adjacent countries would have the same color. Thus, we must give each of the seven countries a different color, so this map is not 6-colorable.