\documentclass[10pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[small]{titlesec}
\usepackage{palatino, mathpazo}
\usepackage{inconsolata}
\usepackage{amsmath, amssymb}
\usepackage{enumitem}
\usepackage{graphicx}
\usepackage[normalem]{ulem}
\usepackage{tikz}
\usepackage{wasysym}
\newcommand{\ds}{\displaystyle}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.5ex}
\title{\sc Math 4670 / 5670 -- Combinatorics\\Homework 6}
\author{
Spring 2022\\[10pt]
due \textbf{\underline{Monday}}, May 9, \underline{by the beginning of class}\\[10pt]
}
\date{}
\begin{document}
\maketitle
\begin{center}
\emph{This homework assignment was written in \LaTeX{}. You can find the source code on the course website.}
\end{center}
\textbf{Mathematical Writing:} An important component of this course is learning how to write mathematics correctly and concisely. Your goal should always be the convince the reader that you are correct! That means explaining your thinking and each step in your solution. I expect you to do the following: explain your reasoning, don't leave out steps, and use full sentences with correct spelling and grammar (including your use of math symbols).
\textbf{\underline{All answers must be fully justified to receive credit.} Answers without justification will not be considered correct.}
\begin{enumerate}
\item A school is preparing the schedule of classes for the next academic year. They are concerned about scheduling calculus, physics, English, statistics, economics, chemistry, and German classes, planning to offer a single section of each one. Below are the lists of courses that each of six students must take in order to successfully graduate. Use graph theory to determine the smallest number of class periods that can be used to schedule these courses if each student can take at most one course per class period. Explain why fewer class periods cannot be used.
\begin{center}
\begin{tabular}{cl}
Student & Courses\\\hline
1 & Chemistry, Physics, Economics\\
2 & English, German, Statistics\\
3 & Statistics, Calculus, German\\
4 & Chemistry, Physics\\
5 & English, Chemistry\\
6 & Chemistry, Economics
\end{tabular}
\end{center}
\item All trees with more than one vertex have the same chromatic number. What is it, and why?
\item Let $G = (V, E)$ be a graph with $V = \{v_1, v_2, \ldots, v_n\}$. Its \emph{degree sequence} is the list of the degrees of its vertices, arranged in nonincreasing order. That is, the degree sequence of $G$ is
\[
(\deg(v_1), \deg(v_2), \ldots, \deg(v_n))
\]
with the vertices arranged such that
\[
\deg(v_1) \geq \deg(v_2) \geq \cdots \geq \deg(v_n).
\]
Below are five sequences of integers (along with $n$, the number of integers in the sequence). Identify
\begin{itemize}
\item the \emph{one} sequence that cannot be the degree sequence of any graph;
\item the \emph{two} sequences that could be the degree sequence of a planar graph;
\item the \emph{one} sequence that could be the degree sequence of a tree;
\item the \emph{one} sequence that is the degree sequence of a graph with an Eulerian circuit;
\item the \emph{one} sequence that is the degree sequence of a graph that must be Hamiltonian.
\end{itemize}
\begin{enumerate}
\item $n=10: (4,4,2,2,1,1,1,1,1,1)$
\item $n=9: (8,8,8,6,4,4,4,4,4)$
\item $n=7: (5,4,4,3,2,1,0)$
\item $n=10: (7,7,6,6,6,6,5,5,5,5)$
\item $n=6: (5,4,3,2,2,2)$
\end{enumerate}
\item Is a graph uniquely determined by its degree sequence? In other words, if I give you just the degree sequence of a graph, is there only one possible graph that has that degree sequence? If yes, prove it. If no, give a counterexample.
\item Find a planar drawing of the graph $K_5 - e$, by which we mean the graph formed from the complete graph on $5$ vertices by deleting any edge.
\item Suppose $G = (V, E)$ is a bipartite graph with parts $A$ and $B$ (i.e., $A \cup B = V$, $A \cap B = \emptyset$, and there are no edges between any two vertices in $A$ or between any two vertices in $B$). Prove that
\[
\sum_{v \in A} \deg(v) = \sum_{v \in B} \deg(v).
\]
\item A graph is called \emph{regular} if every vertex has the same degree. Prove that if $G$ is a regular graph in which every vertex has degree $d \geq 1$, then every bipartite decomposition of the vertices of $G$ into parts $A$ and $B$ must have the property that $|A| = |B|$.
\end{enumerate}
\end{document}