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

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

\begin{document}
\headers{Math378}{Homework 5}{Due Fri. Feb 20, 2026}

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

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

\newcommand{\RR}{\mathbb{R}}
\newcommand{\ZZ}{\mathbb{Z}}

\makeatletter
\def\@oddfoot{}
\makeatother

\noindent
\textbf{Directions:} Solve the following problems.  All written work must be your own.  See the course syllabus for detailed rules.

\begin{enumerate}

\item {} [2.1.\{25,26\}] Recall that the \emph{slope} of the line segment joining the pair of points $(x_1,y_1)$ and $(x_2,y_2)$ in the plane is $(y_2 - y_1)/(x_2 - x_1)$.
\begin{enumerate}
	\item Prove that if $S$ as a set of 17 points in the plane, no two of which are on a common vertical or horizontal line, then there exist $p_1,\ldots,p_5\in S$ such that the slope of the line segments joining $p_i$ and $p_j$ for $1\le i < j \le 5$ all have the same sign.
	
	\item Give an example that shows that the conclusion of part (a) does not always hold if we assume only that $|S| \ge 16$.
\end{enumerate}


\item {} [2.2.3] What is the maximum number of edges in an $n$-vertex bipartite graph?  Prove your answer is correct.

\item {} [2.2.6] Each of 9 users sends three friend requests on a social media platform.  Is it possible that each person $p$ receives exactly 3 friend requests from the same three people to whom $p$ sent the requests?  What if the number of users is 8 instead?

\item {} [2.2.13] Show that the two graphs below are isomorphic.
\begin{center}
~\hfill
\begin{tikzpicture}[vertex/.style={inner sep=2pt,fill=black!50,circle,minimum size=0.5ex},baseline=0pt]
	\scriptsize
	\foreach \n/\anch in {0/north west,1/south west, 2/south, 3/south east, 4/north east}
	{{
		\pgfmathsetmacro{\ang}{\n * (360/5) + 18}
		\path (\ang:1cm) node[vertex] (V\n) {}  node[anchor=\anch,inner sep=4pt,minimum size=0pt] {$v_{\n}$} ;
		\path (\ang:2cm) node[vertex] (U\n) {} ++(\ang:0.3cm)node {$u_{\n}$} ;
	}}
	
	\foreach \n in {0,...,4}
	{{
		\draw (U\n) edge (V\n) ;
		
		\pgfmathsetmacro{\nextout}{int(mod(\n + 1, 5))}
		\pgfmathsetmacro{\nextin}{int(mod(\n + 2, 5))}
		\draw (U\n) edge (U\nextout) ;
		\draw (V\n) edge (V\nextin) ;
	}}
	
	\normalsize
	\path (-90:2.5cm) node[anchor=north] {$G$} ;	
\end{tikzpicture}
\hfill
\begin{tikzpicture}[vertex/.style={inner sep=2pt,fill=black!50,circle,minimum size=0.5ex},baseline=0pt]
	\scriptsize
	\foreach \n in {0,...,8}
	{{
		\pgfmathsetmacro{\ang}{\n*(360/9)}
		\path (\ang:2cm) node[vertex] (W\n) {} ++(\ang:0.3cm) node {$w_{\n}$} ;
	}}
	
	\foreach \n in {0,...,8}
	{{
		\pgfmathsetmacro{\succ}{int(mod(\n+1,9))}
		\draw (W\n) edge (W\succ) ;
	}}
	
	\path node[vertex] (W9) {} ++(-0.3cm,0) node {$w_9$} ;
	\foreach \n in {0,3,6}
	{{
		\draw (W\n) edge (W9) ;
	}}
	
	\foreach \n in {1,4,7}
	{{
		\pgfmathsetmacro{\succ}{int(mod(\n + 4, 9))}
		\draw (W\n) edge[bend right] (W\succ) ;
	}}
	
	\normalsize
	\path (-90:2.5cm) node[anchor=north] {$H$} ;	
\end{tikzpicture}
\hfill ~
\end{center}



\end{enumerate}
\end{document}
