\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,kgm}

\newcommand{\kgmcomment}[1]{}
\renewcommand{\gcd}{\mathrm{gcd}}

\begin{document}
\headers{Math378}{Quiz 5}{Wed. Feb 25, 2026}
\setlength{\columnseprule}{0.4pt}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

%\newcommand{\seq}[1]{\left\langle #1\right\rangle}

\newcommand{\compicon}%
{%
	\begin{tikzpicture}[scale=0.15]%
		\draw[double] (0,0) rectangle (1,1) ;
		\begin{scope}[yshift=-5pt]
			\draw (-0.5, -0.5) rectangle (1.5, 0) ;
		\end{scope}
	\end{tikzpicture}
}

\makeatletter
\def\@oddfoot{}
\makeatother

\noindent
\hfill Name: \underline{\hspace{3.5in}} 

\noindent
\textbf{Directions:} Show all work.  

\begin{enumerate}
\item\points{2} Give a list of distinct integers of maximum possible length that does not contain an increasing subsequence of length $5$ or a decreasing subsequence of length $4$.
\vfill

\item\points{2} Give a formula for the number of edges in the $n$-vertex complete graph $K_n$.  Prove that your answer is correct.
\vfill

\item\points{2} Construct a $6$-vertex bipartite graph with $9$ edges.
\vspace{3cm}

\newpage
\item\points{2} Are the following graphs isomorphic?  If so, then give an isomorphism.  If not, then give a property that distinguishes the graphs.%
\begin{center}
~\hfill
\begin{tikzpicture}[vertex/.style={inner sep=1pt,circle,draw,minimum size=4ex},baseline=0pt]
	\tiny
	\foreach \lab/\x/\y in {%
		a/0/0, b/1/1, c/2/1, d/3/1, e/4/0,%
		f/0/3, g/1/2, h/2/2, i/3/2, j/4/3%
		}
	{{
		\node[vertex] at (\x,\y) (U\lab) {$\lab$} ;
	}}
	
	\foreach \u in {a,e}
	{{
		\foreach \v in {b,c,d}
		{{
			\draw (U\u) -- (U\v) ;
		}}
	}}

	\foreach \u in {f,j}
	{{
		\foreach \v in {g,h,i}
		{{
			\draw (U\u) -- (U\v) ;
		}}
	}}
	
	\foreach \u/\v in {a/f, b/g, c/h, d/i, e/j}
	{{
		\draw (U\u) -- (U\v) ;
	}}		
\end{tikzpicture}
\hfill
\begin{tikzpicture}[vertex/.style={inner sep=1pt,circle,draw,minimum size=4ex},baseline=-1.55cm]
	\tiny
	\foreach \n in {0,...,9}
	{{
		\pgfmathsetmacro{\ang}{int(36*\n - 18)}
		\node[vertex] at (\ang:1.6cm) (V\n) {$\n$} ;
	}}
	
	\foreach \n in {0,...,9}
	{{
		\pgfmathsetmacro{\succ}{int(mod(\n+1,10))}
		\draw (V\n) -- (V\succ) ;
	}}
	
	\foreach \n in {1,2,4,6,7,9}
	{{
		\pgfmathsetmacro{\dst}{int(mod(\n + 3, 10))}
		\draw (V\n) -- (V\dst) ;
	}}
	
	\draw (V3) -- (V8) ;
\end{tikzpicture}
\hfill ~
\end{center}
\vfill

\item\points{2} Let $G$ be an $n$-vertex $m$-edge graph.  Prove that $G$ contains a vertex $u$ whose degree $d(u)$ is at least $2m/n$.  
\vfill


\end{enumerate}
\end{document}
