# Hypercube graph

Let $Q_n$ be the hypercube graph.

• $Q_1 = K_2$ (the complete graph with two vertices),
• $Q_2 = C_4$ (the square), and
• $Q_n$ is constructed taking two copies of $Q_{n-1}$ and adding an edge that connects each vertex of the first copy with the corresponding vertex of the second copy.

Easy: Find $\chi(Q_n)$ (chromatic number) for every $n$.

Harder: Find every $n$ such that $Q_n$ is planar.

# Graph minors

A graph $H$ is a minor of a graph $G$ if $H$ is isomorphic to a graph obtained by contracting edges, removing edges and/or removing isolated vertices from $G$. For example the graph with two vertices and one edge is a minor of any graph with at least one edge.

Problem: Fix a graph $H$. Find a polynomial time algorithm that decides if a given graph $G$ has $H$ as one of its minors. The algorithm must be polynomial in the number of vertices of $G$.

Notice that such an algorithm proves that planarity of a graph can be decided in polynomial time.

# 3

Let $G$ be a simple graph such that $\mathrm{diam}(G) \geq 3$. Then $\mathrm{diam}(G^c) \leq 3$. Moreover, if $\mathrm{diam(G)} > 3$ then $\mathrm{diam}(G^c) < 3$.

Reminders: $G^c$ is the complement graph,  so $V(G) = V(G^c)$ and $e \in E(G^c) \iff e \not \in E(G)$. $\displaystyle \mathrm{diam(G)} = \max_{v_i, v_j \in V(G)} d(v_i, v_j)$. For example, $\mathrm{diam}(K_n) = 1$.

# Intersection number of graphs

Given two graphs $G,H$, draw them in the plane, in such a way that the drawings intersect in interior point of edges, and in such a way there are finitely many points of intersection. The intersection number of $G,H$ with respect to this drawing is the sum of the number of intersections reduced modulo two. Convince yourself this might depend on the way we draw $G,H$. Define the self intersection number of $G$ with respect to a good drawing as above to be the sum of self intersections between non-adjacent edges. This might also depend on the drawing. Of course, a planar graph admits $0$ as its intersection number, but might also admit $1$, as the canonical drawing of $K_{2,3}$ shows.

1. Show that if $G,H$ are cycles, their intersection number is well defined, and is in fact zero.
2. Suppose $G$ has the property that for any edge $e$ in $G$ the nonadjacent edges to $e$ form a cycle. Show that the self intersection number is well defined.
3. Conclude that $K_{3,3}$ and $K_5$ are not planar by showing they have self intersection number equal to one and satisfy the condition above.

# Rock, paper, scissors

Explain why there is a “Rock, paper, scissors” game and a “Rock, paper, scissors, lizard, Spock” game, but there cannot be a “Rock, paper, scissor, lizard” game.

# Triangles in a simple graph

Let $G$ be a simple (no loops, no parallel arrows) graph with $E$ edges and $V$ vertices. Then $G$ contains at least $\dfrac{E}{3V}(4E-V^2)$ triangles.

# Points on the unit circle

This problem is from Stanley’s “Enumerative Combinatorics Vol. I”, more precisely problem 12 from Chapter 1 (sadly, no solution is provided there.)

Consider $n$ points arranged in the unit circumference and draw all $\binom n2$ chords connecting two of the points. Assume that the points are laid out in such a way no three chords intersect in a single point (that is, there are no triple intersections). Into how many regions will the interior of the circle by divided? Stanley says: “Try to give an elegant proof avoiding induction, finite differences, generating functions, summations, and the like.” One can do such a thing.

There’s another problem that involves placing points in the circle. Place $2n$ points in the circle, and label $n$ of them with a $1$, and the remaining $n$ with a $-1$. Prove we can trace the circle, starting from on of this points, in such a way that the partial sums of the values of the points is always positive, and this can be done both clockwise and anticlockwise. Can you generalize this to a continuous (as opposed to discrete) setting?