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

\input{preamble.tex}

\begin{document}

\homework{3}{Week 3}

Attempt the problems that seem interesting!  Easier exercises are marked with $(-)$ signs; harder ones are marked by $(*)$.  Open questions are denoted by writing $(**)$, as they are presumably quite hard.  Oh!  Also, typos build character: if you find any (not that there ever could be such things in my problem sets,) correct them to the most reasonable thing you can think of and proceed from there!

Also also!  I have too many typos in my notes.  If you find any, let me know!  I will offer rewards!  (Rewards to be defined soon.  Rewards will typically not be granted for grammatical or spelling errors, as frustrating/embarrassing as they are.)

\begin{enumerate}
\item If we didn't get to proposition 4 on today's lecture (if a graph has diameter $d$, it must have at least $d+1$ distinct eigenvalues,) prove it without looking at the notes!
\item Similar to yesterday's problem: either find a graph that has $\sqrt{3 + \sqrt{11}}$ as an eigenvalue, or show that no such crazy thing can exist.
\item For most of this class, we're going to work with the \textbf{adjacency matrix} of a given graph.  However, there are other perfectly excellent ways to turn graphs into matrices!  One such way is the \textbf{Laplacian matrix}, which we define here:
\begin{definition}
Given a graph $G$, the \textbf{Laplacian matrix} of $G$ is the matrix $L_G$ defined by
\begin{align*}
L_G = \left\{ l_{ij}: l_{ij} = \left\{ \begin{array}{cc} -1, & (i,j) \in E(G) \\ 0, & (i,j) \notin E(G), i \neq j \\ \deg(i), & i=j \\ \end{array}   \right. \right\}
\end{align*}
\begin{enumerate}
\item $(-)$ Show that this matrix has at least one 0 as an eigenvalue.
\item $(-)$ Show that if $G$ has diameter $d$, the Laplacian matrix also has at least $d+1$ distinct eigenvalues.
\item Show that if 0 is an eigenvalue of $L_G$ with multiplicity $k$, then $G$ has $k$ distinct connected components.
\item Show that if $G$ is regular with degree $k$, then $L_G$'s largest eigenvalue is $k$, and its multiplicity is the number of connected components of $L_G$.
\end{enumerate}
\end{definition}
\item Find the spectrum of the complete bipartite graphs $K_{m,n}$.
\item (Proving Easy Things The Dumb Way):  Show, using pretty much \textbf{only} your knowledge of their spectra, that $K_{11}$ cannot be written as the edge-disjoint union of two bipartite graphs.
\end{enumerate}


\end{document}