


\documentclass[11pt]{article}
\usepackage{graphicx}
\usepackage{fullpage}
\usepackage{enumerate}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{hyperref}
\usepackage{multicol}
\usepackage{soul}
\usepackage{graphicx}                                          
\usepackage{float}                                                

\vfuzz2pt 
\hfuzz2pt 

\newtheorem{thm}{Theorem}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[thm]{Remark}
\newtheorem*{fact*}{Fact}
\numberwithin{equation}{section}

\newtheoremstyle{probstyle}  
{3ex}                        
{0pt}                        
{\normalfont}                
{-3ex}                       
{\normalfont\bfseries}       
{.}                          
{.5em}                       
{}                           
\theoremstyle{probstyle}
\newtheorem{problem}{Problem}

\newcommand{\abs}[1]{\left\vert#1\right\vert}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\R}{\mathbb R}
\newcommand{\eps}{\varepsilon}
\setlength\parindent{0pt}
\setul{.25ex}{}

\begin{document}
	\title{Math 154 Homework \#7\vspace{-3ex}}
\date{Spring 2023}
	\maketitle
	\begin{center}
		Due date: \textbf{11:59pm} Pacific Time on \textbf{Wed, May 31} (via \href{https://www.gradescope.com/}{Gradescope})
	\end{center} 
	\vskip 3ex
	\thispagestyle{empty}
	
	\noindent\emph{On the first page of your work, please write a list of everyone with whom you collaborated on this assignment, as well as any outside sources you consulted, apart from the textbook, your notes, and the course staff. If you did not collaborate with anyone, please explicitly write, ``No collaborators."}\\

	
	\begin{problem}\label{prob:complement}   The \textbf{complement} $\overline{G}$ of a graph $G$ is the graph on the same vertex set where \mbox{$\{u,v\} \in E(\overline{G})$} if and only if $\{u,v\} \notin E(G).$
		(In other words, to obtain the complement $\overline{G}$ of $G$, we fill in all the edges missing from $G$ to form a complete graph, then delete the edges originally present in $G$.)
		\begin{enumerate}[(a)]
			\item Prove that, for every graph $G$ on 11 or more vertices, at most one of $G$ and $\overline{G}$ can be planar. \\
			\textit{(If you get stuck, there is a hint on the last page.)}
			\item Give an example of a graph $G$ on 11 or more vertices where both $G$ and $\overline{G}$ are nonplanar.\\ 
		\end{enumerate}
	\end{problem}
	
	\begin{problem} 
	Determine whether the graph $G$ below is planar or not planar. If it is planar, prove it by explicitly drawing a planar embedding of $G$. If it is not planar, use Kuratowski's Theorem: identify a subgraph that is a subdivision of $K_5$ or $K_{3,3}$, and draw $G$ with that subgraph clearly highlighted.
	
	\begin{figure}[H]
		\centering
		\begin{minipage}{.37\textwidth}
			\includegraphics[width=1\linewidth]{./hw7_graph}
			
		\end{minipage}
	\end{figure}
	\end{problem}	
	
	\begin{problem}\label{prob:4color} 
		Show that every triangle-free planar graph is 4-colorable.
		\\\textit{(Note: do not use the 4-Color Theorem!)}
	\end{problem}
	
	\begin{problem}\label{prob:ERplanar} (Bonus -- NOT TO BE TURNED IN)
		The \textbf{Erd\"os-Renyi random graph} $G(n,1/2)$ is a graph on $n$ vertices constructed as follows: between each pair of vertices, we place an edge independently with probability $\frac{1}{2}$. (Note: this is one way of choosing a graph uniformly at random from among all graphs on $n$ vertices.)\\
		
		Show that $G(n,1/2)$ is nonplanar with probability approaching 1 as $n\to\infty$.\\
		
		\textit{(If you've taken Math 180A before, you have all the tools to do this!)} 
		
		
	\end{problem}
	
	

	
	
	\newpage
	

	
	\textbf{Hint for Problem \ref{prob:complement}:} How many edges and vertices does $\overline{G}$ have?  \\
	
		
	
\end{document} 
