\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\def\zero{\multicolumn{1}{>{\columncolor{white}}c}{0}}
\def\colCell#1#2{\multicolumn{1}{>{\columncolor{#1}}c}{#2}}

\input{preamble.tex}

\begin{document}
\homework{7: Graphs (Fundamentals)}{Due Friday, Week 5}

Do \textbf{three} of the five problems listed here!  Have fun, prove all of your claims, and let me know if you have any questions!

\begin{enumerate}
\item \begin{enumerate}
\item Suppose that $G$ is a graph on $n$ vertices with $m$ edges, where $n \geq 4$ and $m > \frac{n^2}{4}$.  Prove that $G$ contains an odd-length cycle as a subgraph.
\item For any even $n$, create a graph on $n$ vertices with $\frac{n^2}{4}$ edges that does not contain an odd-length cycle as a subgraph.
\end{enumerate}
\item Given a graph $G$, its \textbf{complement} is the graph $\overline{G}$ formed as follows:
\begin{itemize}
\item The vertices of $\overline{G}$ are the same as the vertices of $G$.
\item We connect two vertices in $\overline{G}$ with an edge if and only if they are not connected by an edge in $G$.
\end{itemize}
\begin{center}
\includegraphics[width=1in]{graph_comp.pdf}
\end{center}
\begin{enumerate}
\item Show that for any graph $G$, at least one of $G, \overline{G}$ are connected.
\item A graph is called \textbf{self-complementary} if $G$ is isomorphic to $\overline{G}$. 
\begin{center}
\includegraphics[width=1in]{graph_self_comp.pdf}
\end{center}
\end{enumerate}
Prove that if $n$ is a multiple of 4, there is a self-complementary graph on $n$ vertices.
\item Take a graph $G$.  An \textbf{automorphism} of $G$ is any isomorphism from a graph to itself. For example, take the graph $G$ from above.  It has two automorphisms:\ one where we send $v(1) = 1, v(2) = 2, v(3) = 3, v(4) = 4$, and another where we send $v(1) = 2, v(2) = 1, v(3) = 4, v(4) = 3$.  
\begin{center}
\includegraphics[width=1.4in]{graph_auto.pdf}
\end{center}
\begin{enumerate}
\item Prove that the two automorphisms listed above are the only automorphisms of the graph $G$ as drawn.
\item Take any graph $G$, and let $\varphi, \psi$ denote a pair of automorphisms of $G$ (i.e.\ a pair of isomorphisms from $G$ to $G$.)  Prove that $\varphi \circ \psi$, the map created by composing these two functions, is also an automorphism.
\item Let $Aut(G)$ denote the collection of all of the automorphisms from a graph to itself. Prove that $Aut(G)$ is a group.
\end{enumerate}
\item Take a connected graph $G$.  We defined a notion of \textbf{distance} on the vertices of a graph last week as follows: for any two vertices $x, y\in V(G)$, we say that $d(x,y)$ is equal to the length of the shortest path in $G$ that connects $x$ and $y$.

Prove that this notion of distance is a metric.
\item Given a connected planar graph $G$, we can form the \textbf{dual} to this graph, $G^*$, as follows:
\begin{itemize}
\item Vertices of $G^*$: the faces of $G$.
\item Edges of $G^*$: connect two faces $F_1$, $F_2$ if they share an edge in common.
\end{itemize}
\begin{enumerate}
\item Prove that $G^*$ is a connected planar graph.
\item Show that the dual of $G^{*}$, i.e. $(G^{*})^{*}$, is just the graph $G$ again.
\item Draw the five platonic solids as planar graphs.
\item Find the dual of each solid.
\end{enumerate}
\end{enumerate}



\end{document}