Jozsef Solymosi

Office: MATH 116

MATH 309 Section 201

Term II, 2011-12

Topics in Geometry

Prerequisite: One of MATH 152, MATH 221, MATH 223 and one of MATH 220, MATH 226, CPSC 121. Specifically, it will be assumed that students are familiar with basic techniques of mathematical proof and reasoning such as induction and proof by contradiction. Students will be expected to write logically correct and mathematically coherent proofs as part of homework and examinations.

The course syllabus will be as follows:

• Euler’s formula. Convexity, Graphs, Trees, Convex Polyhedron, Planar Graphs.

• Planar Graphs. Drawings, Colouring, Structure, Kuratowski’s Theorem.

• Geometric Graphs. Drawings, Intersections, Crossings.

• Crossing Number. Basic Probability, Upper and Lower Bounds.

• Point-Line incidences. Szemeredi-Trotter Theorem (bounds on incidences)

• Metric problems in Discrete Geometry. The unit distances problem, distinct distances.

• Combinatorics of point-sets. Erdos-Szekeres Theorem, Halving lines.

• Circle Packing. Planar circle packing, Lattice Packing, Sphere Packing.

• Geometry of Numbers. Pick’s Theorem, Minkowski’s Theorem, applications.

Evaluation: There will be two midterm exams and one final exam, as well as weekly homework assignments. Homework will be assigned on Thursdays, and due the following Thursday in class. Late homework will not be accepted.

The course mark will be computed as follows:

Final Exam: 50 percent

Midterm Exams: 20 percent x 2 = 40 percent

Homework: 10 percent

You are required to be present at all examinations. No makeup tests will be given. Non-attendance at an exam will result in a mark of zero being recorded.

What to study?

The book “Proofs from the BOOK” contains most of the material we've learned related to Euler’s formula.

You can read this book online via the UBC library. Read Chapter 12, “Three applications of Euler’s formula” up to Sylvester’s problem.

Here is the first practice midterm with solutions:

Question 1. Prove that every planar graph is five colourable.

(If you can't remember the proof then you will find it in many elementary graph theory book or on the web. e.g.: http://en.wikipedia.org/wiki/Five_color_theorem, but try to prove it first)

Question 2. Illustrate the convex hull of the following point sets in the plane. Which are the vertices of the convex hull? Write the other points as a convex combination of some of the vertices.

{(0,1), (-2,-1), (4,-1), (1,1), (1,0)}.

I can't attach a picture now. Check the practice questions similar to this one.

(1,0) is a convex combination of the points (-2,-1), (4,-1), (1,1). (You can choose another triple if you want)

We are looking for nonnegative a1,a2, and a3 such that a1+a2+a3=1 and a1(-2,-1)+a2(4,-1)+a3(1,1)=(1,0) .

So we have three linear equations, one for convexity (the sum=1) and two for the above equation for each coordinates.

You solve

a1+a2+a3=1

a1*(-2)+a2*4+a3=1

a1*(-1)+a2(-1)+a3=0

to get

a1=1/4, a2=1/4, and a3=1/2 .

Question 3. Given a planar graph on 17 vertices. Suppose that there is a drawing of this graph with 17 faces (countries). Show that the graph has a vertex with degree 3 or less.

Solution: By Euler's formula we know that the number of edges is 32. The sum of the degrees is 32*2=64, so the average degree is 64/17=3.76470588 < 4. The average is smaller than 4, therefore there should be at least one vertex with degree less then 4.

Question 4. Prove that the  Grötzsch Graph is not planar.

Solution: The graph has 11 vertices and 20 edges.  We know that any simple triangle-free planar graph on v ≥ 3 vertices has at most 2v − 4 edges. This graph has no triangles and has 20> 2*11-4=18 edges, therefore it can't be planar.

Question 5. Given a planar graph G such that all but four vertices have degree four or less. Prove that G is four-colourable.

Solution: We prove the statement by induction. Every graph on four vertices is four-colourable. Now let us suppose that the statement holds for graphs on n vertices for some n>4. We show that then it holds for graphs on n+1 vertices as well. Draw the n+1-- vertex graph G on the plane and choose a vertex v with degree four or less. Colour the graph without v using four colours. If the neighbours of v were coloured by less than four colours then we can colour v by the fourth colour. If we used four colours then we will modify the colouring so that eventually we will use three colours for the neighbours of v.  The colours of the neighbours are black (v1), white (v2), red (v3), and blue (v4) in clockwise order. Let us consider the subgraph of G spanned by the black and red vertices.

There are two cases:

a, The two vertices v1 and v3 are not connected in the graph spanned by the black and red vertices. In this case we can simply swap the colouring of the black and red vertices in the connected component of  v1 in the spanned subgraph. After that colour v by black to colour G by using four colours.

b, The two vertices v1 and v3 are connected in the graph spanned by the black and red vertices. In this case the two vertices v2 and v4 can't be connected in the graph spanned by the white and blue vertices.  Swap the colouring of the white and blue vertices in the connected component of  v2 in the spanned subgraph. After that colour v by red.

The notes below contain most of the material we've learned related to transformations, symmetries, and lattices.

There is also a collection of practice problems:

Here are some practice questions for convexity.

Here are the solutions.

Here are the solutions of the second midterm.

The notes below contain most of the material we've learned related to the crossing number and applications including Szemerdi-Trotter.

The crossing number inequality « What's new

From: terrytao.wordpress.com/2007/09/18/the-crossing-number-inequality/

Here are the practice questions for the crossing number.

are two more practice questions for the crossing number.

Homework assignments

Solutions

HW #1

Question 2.  What is the minimum number of edges one should erase from K6 (the complete graph on 6 vertices) to make the remaining graph planar?

(a) show that one should remove at least 3 edges.

Solution one:

Suppose that there is a planar drawing of G which is K6 minus 2 edges. The number of countries (faces) is denoted by  f, the number of edges is 13, and the number of vertices is 6. By Euler's formula we know that 6-13+f=2, so f=9. However, every country has at least three borders. The number of borders is exactly twice the number of edges (Both sides of an edge define a border). On one hand every country has at least three borders, therefore 3f  should be at most as large (smaller or equal) as twice the number of edges. On the other hand 3*9=27 is larger than 2*13=26. This is a contradiction, so G can not be planar.

Solution two:

We saw in class that if G is a planar graph on n > 2 vertices then the number of edges  is at most 3n-6. In our case that means that the number of edges is at most 3*6-6=12 as needed.

Question 3. What is the minimum number of edges one should erase from K3;4 (the complete bipartite graph on 3+4 vertices) to make the remaining graph planar?

(a) show that one should remove at least 2 edges.

Solution:

Let us suppose that one can remove one edge of K3;4 and there is a planar drawing of this graph. By Euler's formula  7-11+f=2, so f=6.  Since K3;4  was a bipartite graph, every country has at least four borders. By the same argument we had in Solution one of the previous question, we know that 4*f =24 should be smaller or equal than 2*11=22. This is a contradiction, so we know that K3;4 minus an edge can't be planar.

HW #2

2.      Exercises:

a.       (2 points) Prove the following statement: If a tree has a vertex with degree k, then the tree has at least k vertices having degree one.

Solution one:

Note that every tree (with at least two vertices) has at least two vertices with degree one.

Proof: Consider the longest path in the tree. The two end-vertices of the path have degree one otherwise we could extend the path to a longer one.

Now let us suppose that vertex v has degree k. If we remove v from the graph then we have k trees left. If a tree has one vertex only then it had degree one in the original tree. If the tree has at least two vertices then it has at least two degree one vertices and at most one of them was connected to v. The second one had degree one in the original graph.

Solution two:

One can argue that we can start k walks from v using the k edges connected to v. Continue each walks as long as we can without going back along an edge we used already. All k walks will end when we cant go any further without turning back. The endpoints of these walks should have degree one, as we could continue the walk otherwise.

HW #3

Question 1. The Heawood graph is the graph of the skeleton of the Szilassi polyhedron. (You can find it's picture at

http://mathworld.wolfram.com/HeawoodGraph.html for example)

Prove that it is not planar.

Proof by contradiction: Let us suppose that it is planar and has a good embedding (drawing) into the plane. The smallest cycle has 6 vertices, therefore if the number of faces is denoted by f then the number of borders=2*edges is at least 6f. By Euler's formula we know that f=21-14+2=9. But 2*edges=42 which is less than 6f = 54, it is a contradiction.

Question 2. Prove the Four Colour Theorem for planar graphs with no triangles. Show that if a planar graph is triangle-free then it can be coloured by four colours.

(Hint: maybe such graphs always have a vertex with small degree)

Proof by induction: One can show that a triangle-free planar graph always has a vertex with degree 3 or less (We will prove it later). Then the proof that it is four-colourable goes by induction. Base case: any graph on 4 (or less) vertices is 4-colourable.  Suppose that every triangle-free planar graph on n vertices is 4-colourable. Take any triangle-free planar graph on n+1 vertices. If it has a vertex with degree three or less then remove it, the remaining graph can be 4 coloured by the induction hypothesis. The removed vertex had 3 or less neighbours only so we can colour it using the fourth colour.

All we have to prove is that there is always a vertex having degree 3 or less. We can suppose that the graph is connected and has at least 4 vertices. (If it is not connected than take any connected component of the graph.) Every face has at least 4 borders. Therefore the number of edges is at least 2f. v-e+f=2 implies v-e+e/2 is at least 2. So, on one hand e<=2v-4. On the other hand the sum of the degrees is 2e. If every vertex had degree 4 or larger then 2e would be at least 4v which is not possible since e<=2v-4.

Question 3. Suppose that a planar graph has two connected components (You draw two connected planar graphs next to each other and this will be your new graph). What is the right variant of Euler's formula in this case? Prove your formula!

Proof: The formula is v-e+f=3. For the connected components G1 and G2 the formula v1-e1+f1=2 and v2-e2+f2=2 hold and v=v1+v2, e=e1+e2. So, v-e=4-f1-f2+4 . The components have one country (face) which separates them. It was counted in the formula twice, i.e. f=f1+f2-1.

Question 4. Prove that if a planar graph on n vertices has 2n-5 faces, then it has at least 3 vertices with degree at most 5.

Proof: Using Euler's formula we see that this graph has 3n-7 edges. If all but two vertices had degree 6 or larger then the sum of degrees would be at least 6(n-2) which is more than twice the number of edges 2(3n-7). But the two should be equal, so we see that the graph had at least 3 vertices with degree 5 or less.

Solutions

Here are the questions of HW#6.

And here are the solutions.