\documentclass{article}
\usepackage{amssymb}
\usepackage{multicol}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{verbatim}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{amsmath, epsfig}
\setlength{\parskip}{8pt}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
%\theoremstyle{Remark}
%\newtheorem{remark}
\renewcommand{\today}{}
\newcommand{\abs}[1]{\left| #1\right|}
\newcommand{\Lap}[1]{\mathcal{L}\left\{#1\right\}}


\addtolength{\topmargin}{-.875in}
\addtolength{\textheight}{1.75in}

\newcommand{\solution}[1]{
\begin{quote}\color{red}Solution:\quad 
\color{black} #1
\end{quote}
}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Zplus}{\Z^+}

\begin{document}
\title{Math 228: Homework 6}
\author{Mary Radcliffe}
\date{due 4 Nov 2016}
\maketitle

Complete the following problems. Fully justify each response. You need only turn in those problems marked with a (*).

\begin{enumerate}

\item (*) Let $G$ be a graph, and define $\overline{G}$ to be the graph having $V(\overline{G})=V(G)$, and $E(\overline{G}) = E(G)^c$, that is, $\overline{G}$ has exactly the edges that $G$ doesn't ($\overline{G}$ is called the complement of $G$).

Prove that at least one of $G$ or $\overline{G}$ is connected.

\item Complete exercise 7.3.3 on page 139.

\item (*) Complete exercise 7.3.12 on page 140.

\item (*) Recall that a cut-edge of a graph $G$ is an edge that, when removed, increases the number of connected components of $G$. So, if $G$ is connected, for example, a cut-edge is an edge whose removal leaves a disconnected graph.

\begin{enumerate}
\item Which edges of the graph shown are cut edges?
\vspace{-.8in}
\begin{figure}[htp]
\includegraphics[scale=.6]{cutedges.pdf}
\end{figure}
\vspace{-1.3in}
\item Let $G$ be a connected graph. Prove that $e\in E$ is a cut-edge of $G$ if and only if $e$ is not contained in a cycle of $G$.

\end{enumerate}

\item (*) Let $G$ be a graph. Prove that $G$ is a tree if and only if every two vertices $u, v\in V(G)$ are connected by a unique path.

\item (*) A tree $T$ is called a {\it double star} if it contains exactly two vertices that are not leaves. 

\begin{enumerate}
\item Draw all the double stars on 7 vertices.

\item How many unlabeled double stars are there on $n$ vertices?
\end{enumerate} 

\item Complete exercise 8.5.12 on page 156.
\end{enumerate}

\end{document}