Lesson 1

Basic Problems.

1. (5 points) Can a planar simple graph with \(6\) vertices have \(13\) edges?
   Hint:

   Recall the upper bound on the number of edges in a simple planar graph.
2. (5 points) Show that the Petersen graph has \(K_{5}\) and \(K_{3,3}\) as minors.

   

3. (5 points) For what largest value of \(n\) is the bipartite graph \(K_{3,n}\) planar? What about \(K_{2,n}\)?
   Hint:

   Recall that \(K_{3,3}\) is not planar.
4. (10 points) Does there exist a planar graph with degree sequence \(2,2,3,4,4,5\)?
5. (10 points) Euler's formula says that for a connected planar graph \(G\), \(|V(G)|-|E(G)|+|F(G)|=2\). Assume now that \(G\) has \(k\) connected components. How does Euler's formula look in this case?
   Hint:

   Apply Euler's formula to each component and then account for how the outer faces merge.
6. (10 points) A graph \(G\) has \(11\) vertices. Prove that at least one of \(G\) and \(\overline{G}\) is not planar.
7. (10 points) Show that for any sufficiently large integer \(n\), there exists a simple \(n\)-gon that cannot be guarded by fewer than \(\lfloor n/3 \rfloor\) guards. A guard may be placed anywhere inside the polygon or on its boundary.
8. (10 points) A heptagon is partitioned into convex pentagons and hexagons so that each vertex of the heptagon is a vertex of at least two polygons in the partition. Prove that the number of pentagons in the partition is at least \(13\).

   

9. (15 points) Does there exist a \(4\)-regular planar graph? What about \(5\)-regular and \(6\)-regular? At what minimum \(n\) does a \(5\)-regular planar graph on \(n\) vertices exist?
10. (15 points)
    • (10 points) Prove that for a planar graph \(G(V,E)\) containing a cycle, \[|V|-2\ge |E|\Bigl(1-\frac{2}{g(G)}\Bigr),\] where \(g(G)\) is the girth of \(G\) (the length of its shortest cycle).
    
    
    • (5 points) A planar graph has \(8\) vertices and \(13\) edges. Prove that it is not bipartite.
    
    

    Hint:

    Try to bound the number of faces \(|F|\) in terms of the number of edges \(|E|\) and the girth \(g(G)\).
11. (15 points) In a country, some pairs of cities are connected by roads that do not cross outside of the cities. In each city there is a sign showing the minimum length of a route that starts in that city and passes through all other cities (the route may visit some cities more than once and does not have to return to the starting city). Prove that any two numbers on the signs differ by a factor of at most \(1.5\).
12. (15 points) A graph is called outerplanar if it has a planar drawing in which all vertices lie on the outer face. Prove that every outerplanar graph is \(3\)-colorable.
    Hint:

    Consider using induction on the number of vertices. Try to find a vertex with low degree within the graph. Recall that a triangulation of a polygon always contains “ears.”
13. (15 points) What is the largest number of unit cells of a \(9\times 9\) board that can be cut along both diagonals so that the board does not split into several pieces?

    In the example below, each of the boundary cuts separates the board into two components; therefore, the example given below is not correct.

    

    Hint:

    Model the board as a graph where the cuts are edges and the intersections are vertices.