\documentclass{article}
\usepackage{amsthm, amssymb, amsmath,verbatim}
\usepackage[margin=1in]{geometry}
\usepackage{enumerate}
\usepackage{graphicx}

\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\N}{\mathbb{N}}



\newtheorem*{claim}{Claim}
\newtheorem{ques}{Question}


\title{Math 154 Homework 6}
\date{Fall 2021}

\begin{document}

\maketitle

This homework is due on gradescope by Friday November 12th at 11:59pm pacific time. Remember to justify your work even if the problem does not explicitly say so. Writing your solutions in \LaTeX is recommend though not required.

Please cite any other students with whom you collaborated on any problems.

\begin{ques}[Uniqueness of Planar Embeddings, 40 points]
\begin{enumerate}[(a)]
\item Let $G=(V,E)$ be a connected, planar graph with $|E| = 3|V|-6.$ Show that any two planar embeddings of $G$ have the same set of faces (in particular, that if one embedding has a face whose sides consist of some collection of edges, then the other planar embedding will have a face with the same sides). Hint: Note that $G$ must be triangulated. Consider the faces including a given vertex $v$. [30 points]
\item Show that this is no longer the case if we drop the condition $|E| = 3|V|-6.$ In particular, give a connected, planar graph $G$ with two different embeddings that have different faces. [10 points]
\end{enumerate}
\end{ques}

\begin{ques}[Triangle-less Chromatic Number, 30 points]
Give an example of a graph $G$ which contains no triangle and which has chromatic number at least $4$.
\end{ques}

\begin{ques}[Number of Colorings for Graphs with Small Maximum Degree, 30 points]
Let $G$ be a connected graph with $m$ vertices and let $n\geq \Delta(G)+k$ for some positive integer $k$. Show that there are at least $(k+1)^{m-1}$ ways to color $G$ with any set of $n$ colors.
\end{ques}

\begin{ques}[Extra credit, 1 point]
Free point!
\end{ques}

\end{document} 