\subsection*{Problem 1}
Determine the chromatic number of the complement of a cycle on $n$ vertices.

\begin{proof}
Let $C_n$ be the cycle on $n$ vertices. We know that a proper coloring of the complement graph $\overline{C_n}$ assigns different colors to vertices that are adjacent in $\overline{C_n}$. Vertices are adjacent in $\overline{C_n}$ if and only if they are not adjacent in $C_n$. Therefore, a set of vertices can share the same color in $\overline{C_n}$ if and only if they are ``pairwise non-adjacent'' in $\overline{C_n}$, which means they must be ``pairwise adjacent'' (or the same vertex) in $C_n$. So a valid color class in $\overline{C_n}$ corresponds to a complete subgraph (clique) in $C_n$. The only cliques in a cycle $C_n$ ($n \ge 4$) are single vertices ($K_1$) and edges ($K_2$). There are no cliques of size 3 or larger. Thus, coloring $\overline{C_n}$ is equivalent to partitioning the vertex set $V$ into disjoint edges and vertices. To minimize the number of colors (cliques), we must maximize the number of vertices paired up into edges. Let $k$ be the number of edges ($K_2$) used in the partition. These edges must be disjoint, so $k$ cannot exceed the matching number $\nu(C_n) = \lfloor \frac{n}{2} \rfloor$. The remaining $n - 2k$ vertices must be colored individually (as $K_1$s). The total number of colors used is $\chi(\overline{C_n}) = k + (n - 2k) = n - k$. To minimize this quantity, we must maximize $k$. We choose a maximum matching, so $k = \lfloor \frac{n}{2} \rfloor$, and thus the chromatic number $ \chi(\overline{C_n}) = n - \lfloor \frac{n}{2} \rfloor = \lceil \frac{n}{2} \rceil $. For $n=1$, we have that $\overline{C_n}$ is a single vertex, so the chromatic number is $1=\lceil \frac{1}{2} \rceil$. For $n=2$, we have that $\overline{C_2}$ consists of 2 vertices with no edge between them, so the chromatic number is $1=\lceil \frac{2}{2} \rceil$. For $n=3$, we have $C_3$, which is a triangle $K_3$, and the complement $\overline{C_3}$ is the empty graph on 3 vertices ($3K_1$), where chromatic number is $\chi(\overline{C_3}) = 1 \neq \lceil \frac{3}{2} \rceil$, which is the only exception. Thus, the chromatic number of the complement of a cycle on $n$ vertices is $\lceil \frac{n}{2} \rceil $ for all $n \neq 3$, and when $n=3$, the chromatic number is $1$.
\end{proof}

\subsection*{Problem 2}
Let $G$ be a bipartite graph. Prove that for its complementary graph $\overline{G}$ we have $\chi (\overline{G}) = \omega(\overline{G})$.
\begin{proof}
Let $G$ be a bipartite graph with $n$ vertices. First, observe that a clique in $\overline{G}$ corresponds to an independent set in $G$. Thus, the ``clique number'' (the size of the largest clique) of the complement is the independence number of the original graph, $\omega(\overline{G}) = \alpha(G)$. Next, consider the chromatic number $\chi(\overline{G})$. As shown in the proof for Problem 1, a valid coloring of $\overline{G}$ partitions the vertices of $G$ into cliques of $G$. Since $G$ is bipartite, it contains no cliques of size 3 or greater. Thus, we are partitioning the vertices into disjoint edges and single vertices. If we select a matching $M$ of size $|M|$ in $G$, we can use the edges of $M$ as $|M|$ color classes. The remaining $n - 2|M|$ vertices must be colored individually. The total number of colors is $ |M| + (n - 2|M|) = n - |M| $. To find the chromatic number, we need to minimize this sum, which is the same as maximizing the matching size $|M|$. Thus, we use a maximum matching $\nu(G)$, and so $ \chi(\overline{G}) = n - \nu(G) $. In any bipartite graph, the size of the maximum independent set plus the size of the maximum matching equals the total number of vertices, so $ \alpha(G) + \nu(G) = n \implies \alpha(G) = n - \nu(G)$. Combining our results yields $ \chi(\overline{G}) = n - \nu(G) = \alpha(G) = \omega(\overline{G}) $.
\end{proof}

\subsection*{Problem 3}
Draw some lines in the plane so that no three of them go through the same point. Consider their points of intersection as the vertices of a graph and the segments between neighbouring intersection points on each line as edges. Prove that the chromatic number of the resulting graph is at most $3$.

\begin{proof}
Let the graph created from the process be $G=(V,E)$. The vertices $V$ are the intersection points of the lines. We know that two vertices are connected by an edge if they are consecutive intersection points along one of the lines. Assume that no lines are vertical (since we can rotate the plane a tiny amount if needed). This allows us to order the vertices by their $x$-coordinate. We will show that every subgraph has a vertex of degree at most 2, which would imply that the graph is $3$-colorable. Suppose we have the vertex ordering $v_1, v_2, \dots, v_n$ based on increasing $x$-coordinates. Any vertex $v_i$ is the intersection of exactly two lines, say $L_a$ and $L_b$. Looking to the right of $v_i$ (vertices with higher index), the line $L_a$ continues to its next intersection point, and $L_b$ continues to its next intersection point. So $v_i$ is connected to at most two vertices with an index higher than $i$. This ordering proves that $G$ is 2-degenerate. A coloring algorithm using the reverse of this order (coloring from $v_n$ down to $v_1$) ensures that when we color $v_i$, it has at most 2 neighbors that have already been colored (its ``future'' neighbors in the $x$-ordering). Since there are 3 available colors, there is always a color free for $v_i$. Thus, $\chi(G) \le 3$.
\end{proof}

\subsection*{Problem 4}
For a positive integer $t$, let $f(t)$ denote the minimum number $k$ for which there exists a graph $G$ with $\chi(G) = t$ and $|E(G)| = k$. Determine the value of $f(t)$ for all positive integers $t$.

\begin{proof}
We want the minimum number of edges in a graph with chromatic number $t$. Consider a $t$-critical graph, that is, a graph $G$ with $\chi(G)=t$ such that removing any edge decreases the chromatic number. We know that in a $t$-critical graph, every vertex has degree at least $t-1$. Thus, for $n$ vertices, we have that $|E(G)| \ge \frac{n(t-1)}{2}$. Now, to minimize the number of edges, take the smallest number of vertices possible. A $t$-chromatic graph must have at least $t$ vertices, and the complete graph $K_t$ achieves $\chi(K_t)=t$ with $|E(K_t)| = \frac{t(t-1)}{2}$. Thus, for all positive integers $t$, $f(t) = \frac{t(t-1)}{2}$
\end{proof}

\subsection*{Problem 5}
Let $G$ be a simple graph on $n$ vertices and $\overline{G}$ be its complementary graph. Prove that $\chi(G)\chi(\overline{G}) \geq n$.

\begin{proof}
Let $\chi(G)=a$ and $\chi(\overline G)=b$. Color $G$ with $a$ colors and $\overline G$ with $b$ colors. Here, each vertex is assigned an ordered pair $(i,j)$ where $i\in\{1,\dots,a\}$ is its $G$-color and $j\in\{1,\dots,b\}$ its $\overline G$-color. Note that two distinct vertices cannot share the same pair, since if they did, they would be in the same color class in both $G$ and $\overline G$, so they would be nonadjacent in both $G$ and $\overline G$, which is impossible. Therefore, each of the $n$ vertices receives a distinct pair, giving $ab \ge n$. Thus, $\chi(G)\chi(\overline G) \ge n$.
\end{proof}
