% LaTeX solution template for Math 530
% -----------------------------------------------------------------

% Like most advanced LaTeX files, this one begins with a lot of
% boilerplate. You don't need to understand (or even read) most of it.
% All you need to do is fill in your name, email address,
% and the number of the pset. (Search for "METADATA" to find the place
% for this.) Then, you can go straight to the "EXERCISE 1"
% section and start writing your solutions.
% The "VARIOUS USEFUL COMMANDS" section is probably worth taking a
% look at at some point.

% If you are here to learn about LaTeX, search for
% "START READING HERE" and start reading there.

%----------------------------------------------------------------------------------------
%	PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------
\documentclass[paper=a4, fontsize=12pt]{scrartcl} % A4 paper and 12pt font size
\usepackage[T1]{fontenc} % Use 8-bit encoding that has 256 glyphs
\usepackage[english]{babel} % English language/hyphenation
\usepackage{amsmath,amsfonts,amsthm,amssymb} % Math packages
\usepackage{mathrsfs}    % More math packages
\usepackage{sectsty}  % Allows customizing section commands
\allsectionsfont{\centering \normalfont\scshape} % Make all section titles centered, the default font and small caps %remove this to left align section tites
\usepackage{hyperref} % Turns cross-references into hyperlinks,
                      % and defines \url and \href commands.
\usepackage{graphicx} % For embedding graphics files.
\usepackage{framed}   % For the "leftbar" environment used below.
\usepackage{ifthen}   % Used for the \powset command below.
\usepackage{lastpage} % for counting the number of pages
\usepackage[all,cmtip]{xy} % for commutative diagrams and simple graphs
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[height=10in,a4paper,hmargin={1in,0.8in}]{geometry}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}     % This is a powerful tool to draw vector
                      % graphics inside LaTeX. In particular, you can
                      % use it to draw graphs.
\usepackage{verbatim} % For the "verbatim" environment, in which
                      % special symbols can be used freely without
                      % confusing the compiler. (And it's typeset in
                      % a constant-width font.)
                      % Useful, e.g., for quoting code (or ASCII art).

%\numberwithin{table}{section} % Number tables within sections (i.e. 1.1, 1.2, 2.1, 2.2 instead of 1, 2, 3, 4)

\setlength\parindent{20pt} % Makes indentation for paragraphs longer.
                           % This makes paragraphs stand out more.

%----------------------------------------------------------------------------------------
%	VARIOUS USEFUL COMMANDS
%----------------------------------------------------------------------------------------
% The commands below might be convenient. For example, you probably
% prefer to write $\powset[2]{V}$ for the set of $2$-element subsets
% of $V$, rather than writing $\mathcal{P}_2(V)$.
% Notice that you can easily define your own commands like this.
% Caveat: Some of these commands need to be properly "guarded" when
% they occur in subscripts or superscripts. So you should not write
% $K_\CC$, but rather $K_{\CC}$.
\newcommand{\CC}{\mathbb{C}} % complex numbers
\newcommand{\RR}{\mathbb{R}} % real numbers
\newcommand{\QQ}{\mathbb{Q}} % rational numbers
\newcommand{\NN}{\mathbb{N}} % nonnegative integers
\newcommand{\FF}{\mathbb{F}} % some field
\newcommand{\Z}[1]{\mathbb{Z}/#1\mathbb{Z}} % integers modulo k
                                            % (syntax: "\Z{k}")
\newcommand{\ZZ}{\mathbb{Z}} % integers
\newcommand{\id}{\operatorname{id}} % identity map
\newcommand{\ww}{\mathbf{w}} % a walk
\newcommand{\lcm}{\operatorname{lcm}}
% Lowest common multiple. For historical reasons, LaTeX has a \gcd
% command built in, but not an \lcm command. The preceding line
% rectifies that.
\newcommand{\rank}{\operatorname{rank}}
\newcommand{\conn}{\operatorname{conn}}
\newcommand{\bidir}{\operatorname{bidir}}
\newcommand{\rev}{\operatorname{rev}} % reversal of a walk
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
% $\powset[k]{S}$ stands for the set of all $k$-element subsets of
% $S$. The argument $k$ is optional, and if not provided, the result
% is the whole powerset of $S$.
\newcommand{\set}[1]{\left\{ #1 \right\}}
% $\set{...}$ compiles to {...} (set-brackets).
\newcommand{\abs}[1]{\left| #1 \right|}
% $\abs{...}$ compiles to |...| (absolute value, or size of a set).
\newcommand{\tup}[1]{\left( #1 \right)}
% $\tup{...}$ compiles to (...) (parentheses, or tuple-brackets).
\newcommand{\ive}[1]{\left[ #1 \right]}
% $\ive{...}$ compiles to [...] (Iverson bracket, aka truth value).
\newcommand{\scalp}[1]{\left< #1 \right>}
% $\scalp{...}$ compiles to <...> (scalar product).
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
% $\floor{...}$ compiles to |_..._| (floor function).
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
% $\ceil{...}$ compiles to |°...°| (ceiling function).
\newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)}
% $\verts{...}$ compiles to V(...) (vertex set of a graph/digraph).
\newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)}
% $\edges{...}$ compiles to E(...) (edge set of a graph).
\newcommand{\arcs}[1]{\operatorname{A}\left( #1 \right)}
% $\arcs{...}$ compiles to A(...) (arc set of a digraph).
\newcommand{\lf}[2]{#1^{\underline{#2}}}
% $\lf{...1}{...2}$ compiles to $...1^{\underline{...2}}$.
% This is a notation for the falling factorial.
\newcommand{\are}{\ar@{-}}
% In an xymatrix environment, $\are$ gives an arrow without
% arrowhead. I use this to represent edges in graphs.
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
% $\underbrack{...1}{...2}$ yields
% $\underbrace{...1}_{\substack{...2}}$. This is useful for doing
% local rewriting transformations on mathematical expressions with
% justifications. For example, try this out:
% $ \underbrack{(a+b)^2}{= a^2 + 2ab + b^2 \\ \text{(by the binomial formula)}} $
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}} % Create horizontal rule command with 1 argument of height
\newcommand{\nnn}{\nonumber\\} % Don't number this line in an "align" environment, and move on to the next line.
\newcommand{\explain}[1]{\tup{\hspace{-0.5pc}\text{\begin{tabular}{c}#1\end{tabular}\hspace{-0.5pc}}}}
% $\explain{...}$ interprets the "..." as text (you can
% nest some math inside by putting it in $...$'s as you
% would in any other text block) and puts it in parentheses.

%----------------------------------------------------------------------------------------
%	MAKING SUMMATION SIGNS ALWAYS PUT THEIR BOUNDS ABOVE AND BELOW
%	THE SIGN
%----------------------------------------------------------------------------------------
% The following are hacks to ensure that sums (such as
% $\sum_{k=1}^n k$) always put their bounds (i.e., the $k=1$ and the
% $n$) underneath and above the sign, as opposed to on its right.
% Same for products (\prod), set unions (\bigcup) and set
% intersections (\bigcap). Remove the 8 lines below if you do not want
% this behavior.
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}

%----------------------------------------------------------------------------------------
%	ENVIRONMENTS
%----------------------------------------------------------------------------------------
% The incantations below define how theorem environments
% (\begin{theorem} ... \end{theorem}) and their likes will look like.
\newtheoremstyle{plainsl}% <name>
  {8pt plus 2pt minus 4pt}% <Space above>
  {8pt plus 2pt minus 4pt}% <Space below>
  {\slshape}% <Body font>
  {0pt}% <Indent amount>
  {\bfseries}% <Theorem head font>
  {.}% <Punctuation after theorem head>
  {5pt plus 1pt minus 1pt}% <Space after theorem headi>
  {}% <Theorem head spec (can be left empty, meaning `normal')>

% Environments which make the text inside them slanted:
\theoremstyle{plainsl}
  \newtheorem{theorem}{Theorem}[section]
  \newtheorem{proposition}[theorem]{Proposition}
  \newtheorem{lemma}[theorem]{Lemma}
  \newtheorem{corollary}[theorem]{Corollary}
  \newtheorem{conjecture}[theorem]{Conjecture}
% Environments that don't:
\theoremstyle{definition}
  \newtheorem{definition}[theorem]{Definition}
  \newtheorem{example}[theorem]{Example}
  \newtheorem{exercise}[theorem]{Exercise}
  \newtheorem{examples}[theorem]{Examples}
  \newtheorem{algorithm}[theorem]{Algorithm}
  \newtheorem{question}[theorem]{Question}
 \theoremstyle{remark}
  \newtheorem{remark}[theorem]{Remark}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}

%----------------------------------------------------------------------------------------
%	METADATA
%----------------------------------------------------------------------------------------
\newcommand{\myname}{Darij Grinberg} % ENTER YOUR NAME HERE
\newcommand{\mymail}{darij.grinberg@drexel.edu} % ENTER YOUR EMAIL HERE
\newcommand{\psetnumber}{7} % ENTER THE NUMBER OF THIS PSET HERE

%----------------------------------------------------------------------------------------
%	HEADER AND FOOTER
%----------------------------------------------------------------------------------------
\ihead{Math 530 Homework set \#\psetnumber} % Page header left
\ohead{page \thepage\ of \pageref{LastPage}} % Page header right
\ifoot{\myname} % left footer
\ofoot{\mymail} % right footer

%----------------------------------------------------------------------------------------
%	TITLE SECTION
%----------------------------------------------------------------------------------------
\title{	
\normalfont \normalsize 
\textsc{Drexel University, Department of Mathematics} \\ [25pt] % Your university, school and/or department name(s)
\horrule{0.5pt} \\[0.4cm] % Thin top horizontal rule
\huge Math 530: Graph Theory, Spring 2022: \\
Homework \psetnumber\\% The assignment title
due 2022-05-25 at 11:00 AM \\
\textbf{Please solve 4 of the 8 problems!} \\
\horrule{2pt} \\[0.5cm] % Thick bottom horizontal rule
}
\author{\myname}

\begin{document}

\maketitle % This command causes the title part to be printed.

%----------------------------------------------------------------------------------------
%	EXERCISE 1
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 1}

\subsection{Problem}

Let $D = \tup{V, A, \psi}$ be a multidigraph.
Assume that $V = \set{1, 2, \ldots, n}$ for some positive
integer $n$.
Let $L$ be the Laplacian of $D$.

Prove the following:

\begin{enumerate}

\item[\textbf{(a)}]
If $r$ and $s$ are two vertices of $D$, then
\[
\tup{\# \text{ of spanning arborescences of } D
\text{ rooted to } r}
= \tup{-1}^{r+s} \det\tup{L_{\sim r, \sim s}} .
\]

\item[\textbf{(b)}] For each $r \in V$,
we let $\tau\tup{D, r}$ be the \# of spanning
arborescences of $D$ rooted to $r$.
Let $f$ be the row vector
$\tup{\tau\tup{D, 1},
      \tau\tup{D, 2},
      \ldots,
      \tau\tup{D, n}}$.
Then, $f L = 0$ (the zero vector).

\end{enumerate}

\subsection{Hint}

Part \textbf{(a)} generalizes the
Matrix-Tree Theorem (which is its particular
case for $s = r$).
However, both parts can actually be derived
using the properties of $L$ we know from class
(without any new combinatorial input).

\subsection{Solution}

...

%----------------------------------------------------------------------------------------
%	EXERCISE 2
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 2}

\subsection{Problem}

Let $n$ be a positive integer.
Let $N = \set{1, 2, \ldots, n}$.
A map $f : N \to N$ is said to be
\emph{$n$-potent} if each $i \in N$
satisfies $f^{n-1}\tup{i} = n$.
(As usual, $f^k$ denotes the $k$-fold
composition $f \circ f \circ \cdots \circ f$.)

Prove that the \# of $n$-potent maps
$f : N \to N$ is $n^{n-2}$.

\subsection{Solution}

...

%----------------------------------------------------------------------------------------
%	EXERCISE 3
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 3}

\subsection{Problem}

Let $n = 2m+1 > 2$ be an odd integer.
Let $e$ be an edge of the (undirected)
complete graph $K_n$.
Prove that the \# of Eulerian circuits of $K_n$
that start with $e$ is a multiple of
$\tup{m-1}!^n$.

\subsection{Hint}

Argue that each Eulerian circuit of $K_n$ is a
Eulerian circuit of a unique balanced tournament.
Here, a ``balanced tournament'' means a balanced
digraph obtained from $K_n$ by orienting each edge.

\subsection{Solution}

...

%----------------------------------------------------------------------------------------
%	EXERCISE 4
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 4}

\subsection{Problem}

Let $G = \tup{V, E, \varphi}$ be a multigraph.
Let $L$ be the Laplacian of the digraph
$G^{\bidir}$.
Prove that $L$ is positive semidefinite.

\subsection{Hint}

Write $L$ as $N^T N$, where $N$ or $N^T$ is some
matrix you have seen before.

Note that the statement is not true if we replace
$G^{\bidir}$ by an arbitrary digraph $D$.

\subsection{Solution}

...

%----------------------------------------------------------------------------------------
%	EXERCISE 5
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 5}

\subsection{Problem}

Let $n$ be a positive integer.
Let $Q_n$ be the $n$-hypercube graph (as defined
in Lecture 6).
Recall that its vertex set is the set
$V := \set{0, 1}^n$ of length-$n$ bitstrings, and
that two vertices are adjacent if and only if they
differ in exactly one bit.
Our goal is to compute the \# of spanning trees of
$Q_n$.

Let $D$ be the digraph $Q_n^{\bidir}$.
Let $L$ be the Laplacian of $D$.
We regard $L$ as a $V \times V$-matrix (i.e.,
as a $2^n \times 2^n$-matrix whose
rows and columns are indexed by bitstrings in
$V$).

We shall use the notation $a_i$ for the $i$-th
entry of a bitstring $a$. Thus, each
bitstring $a \in V$ has the form
$a = \tup{a_1, a_2, \ldots, a_n}$.
(We shall avoid the shorthand notation
$a_1 a_2 \cdots a_n$ here, as it could be mistaken
for an actual product.)

For any two bitstrings $a, b \in V$, we define
the number $\scalp{a, b}$ to be the integer
$a_1 b_1 + a_2 b_2 + \cdots + a_n b_n$.

\begin{enumerate}

\item[\textbf{(a)}] Prove that every bitstring
$a \in V$ satisfies
\[
\sum_{b \in V} \tup{-1}^{\scalp{a, b}}
= \begin{cases}
2^n, & \text{ if $a = \mathbf{0}$;} \\
0,   & \text{ otherwise.}
\end{cases}
\]
Here, $\mathbf{0}$ denotes the bitstring
$\tup{0, 0, \ldots, 0} \in V$.

\end{enumerate}

Now, define a further $V \times V$-matrix
$G$ by requiring that its $\tup{a, b}$-th entry
is
\[
G_{a, b} = \tup{-1}^{\scalp{a, b}}
\qquad \text{for any $a, b \in V$}.
\]
Furthermore, define a diagonal
$V \times V$-matrix $D$ by requiring that
its $\tup{a, a}$-th entry is
\begin{align*}
D_{a, a}
&= 2 \cdot \tup{\# \text{ of $i \in \set{1, 2, \ldots, n}$ such that $a_i = 1$}}
\\
&= 2 \cdot \tup{\text{the number of $1$s in $a$}}
\qquad \text{for any $a \in V$}
\end{align*}
(and its off-diagonal entries are $0$).

Prove the following:

\begin{enumerate}

\item[\textbf{(b)}] We have $G^2 = 2^n \cdot I$,
where $I$ is the identity $V \times V$-matrix.

\item[\textbf{(c)}] We have
$GLG^{-1} = D$.

\item[\textbf{(d)}] The eigenvalues of $L$ are
$2k$ for all $k \in \set{0, 1, \ldots, n}$,
and each eigenvalue $2k$ appears with
multiplicity $\dbinom{n}{k}$.

\item[\textbf{(e)}]
The \# of spanning trees of $Q_n$ is
\[
\dfrac{1}{2^n} \prod_{k=1}^n \tup{2k}^{\binom{n}{k}} .
\]

\end{enumerate}

\subsection{Remark}

As an example, here is the case $n = 3$.
In this case, the graph $Q_n$ looks as follows:
\[
\begin{tikzpicture}[scale=2.3]
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(000) at (0, 0) {$000$};
\node(001) at (0, 1) {$001$};
\node(010) at (1, 0) {$010$};
\node(011) at (1, 1) {$011$};
\node(100) at (0.45, 0.45) {$100$};
\node(101) at (0.45, 1.45) {$101$};
\node(110) at (1.45, 0.45) {$110$};
\node(111) at (1.45, 1.45) {$111$};
\end{scope}
\node(X) at (-0.9, 0) {$Q_3 = $};
\begin{scope}[every edge/.style={draw=black,very thick}]
\path[-] (000) edge (001) (001) edge (011) (011) edge (010) (010) edge (000);
\path[-] (100) edge (101) (101) edge (111) (111) edge (110) (110) edge (100);
\path[-] (100) edge (000) (101) edge (001) (111) edge (011) (110) edge (010);
\end{scope}
\end{tikzpicture}
\]
The matrices $L$, $G$ and $D$ are
\begin{align*}
L &= \begin{pmatrix}
3 & -1 & -1 & 0 & -1 & 0 & 0 & 0 \\
-1 & 3 & 0 & -1 & 0 & -1 & 0 & 0 \\
-1 & 0 & 3 & -1 & 0 & 0 & -1 & 0 \\
0 & -1 & -1 & 3 & 0 & 0 & 0 & -1 \\
-1 & 0 & 0 & 0 & 3 & -1 & -1 & 0 \\
0 & -1 & 0 & 0 & -1 & 3 & 0 & -1 \\
0 & 0 & -1 & 0 & -1 & 0 & 3 & -1 \\
0 & 0 & 0 & -1 & 0 & -1 & -1 & 3
\end{pmatrix},
\\
G &= \begin{pmatrix}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 \\
1 & 1 & -1 & -1 & 1 & 1 & -1 & -1 \\
1 & -1 & -1 & 1 & 1 & -1 & -1 & 1 \\
1 & 1 & 1 & 1 & -1 & -1 & -1 & -1 \\
1 & -1 & 1 & -1 & -1 & 1 & -1 & 1 \\
1 & 1 & -1 & -1 & -1 & -1 & 1 & 1 \\
1 & -1 & -1 & 1 & -1 & 1 & 1 & -1
\end{pmatrix},
\\
D &= \begin{pmatrix}
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 2 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 2 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 2 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 4 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 4 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 4 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 6
\end{pmatrix},
\end{align*}
where the rows and the columns are ordered by listing
the eight bitstrings $a \in V$ in the order
$000, 001, 010, 011, 100, 101, 110, 111$.

\subsection{Solution}

...

%----------------------------------------------------------------------------------------
%	EXERCISE 6
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 6}

\subsection{Problem}

Let $n \geq 5$ be an integer.
Let $G$ be the simple graph with vertex set
$\set{1, 2, \ldots, n}$, and with edges
\begin{align*}
12, \ 23, \ 34, \ \ldots, \ \tup{n-2}\tup{n-1}, \ \tup{n-1}n, \ n1, \\
13, \ 24, \ 35, \ \ldots, \ \tup{n-2}n,         \ \tup{n-1}1, \ n2.
\end{align*}
(That is, its edges are $\set{i, i+1}$ and
$\set{i, i+2}$ for all $i \in \set{1, 2, \ldots, n}$,
where we identify the elements $n+1$ and $n+2$
with $1$ and $2$, respectively.)

Prove that the \# of spanning trees of $G$
is $n f_n^2$, where $f_n$ is the $n$-th
Fibonacci number.
(The \emph{Fibonacci numbers} are the
number sequence $\tup{f_0, f_1, f_2, \ldots}$
defined recursively by $f_0 = 0$ and $f_1 = 1$
and $f_k = f_{k-1} + f_{k-2}$ for all $k \geq 2$.)

\subsection{Remark}

Here is the graph $G$ for $n = 6$:
\[
\begin{tikzpicture}[scale=2]
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(1) at (0:2) {$1$};
\node(2) at (60:2) {$2$};
\node(3) at (120:2) {$3$};
\node(4) at (180:2) {$4$};
\node(5) at (240:2) {$5$};
\node(6) at (300:2) {$6$};
\end{scope}
\begin{scope}[every edge/.style={draw=black,very thick}, every loop/.style={}]
\path[-] (1) edge (2) edge (3);
\path[-] (2) edge (3) edge (4);
\path[-] (3) edge (4) edge (5);
\path[-] (4) edge (5) edge (6);
\path[-] (5) edge (6) edge (1);
\path[-] (6) edge (1) edge (2);
\end{scope}
\end{tikzpicture}
\]

\subsection{Solution}

...

%----------------------------------------------------------------------------------------
%	EXERCISE 7
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 7}

\subsection{Problem}

Fix two positive integers $n$ and $k$ with $n \geq 2k > 0$.
Let $S = \set{1, 2, \ldots, n}$.
Consider the $k$-Kneser graph $K_{S,k}$ as defined in
Lecture 3.
Prove that $K_{S,k}$ has a proper
$\tup{n-2k+2}$-coloring.

\subsection{Hint}

What can you say about the minima (i.e.,
smallest elements) of two disjoint subsets
of $S$?
(Being distinct is a good first step.)

\subsection{Remark}

L\'ovasz has proved in 1978 (using topology!)
that this result is optimal -- in the sense that
$n-2k+2$ is the smallest integer $q$ such that
$K_{S,k}$ has a proper $q$-coloring.

\subsection{Solution}

...

%----------------------------------------------------------------------------------------
%	EXERCISE 8
%----------------------------------------------------------------------------------------
\horrule{0.3pt} \\[0.4cm]

\section{Exercise 8}

\subsection{Problem}

Let $n$ and $k$ be two positive integers.
Let $K$ be a set of size $k$.
Let $D$ be the de Bruijn digraph -- i.e., the
multidigraph constructed in the proof of
Theorem 1.1.2 in Lecture 20.
Let $G$ be the result of removing all loops from
the undirected graph $D^{\operatorname{und}}$.
Prove that $G$ has a proper $\tup{k+1}$-coloring.

\subsection{Solution}

...

\horrule{0.3pt} \\[0.4cm]

% Uncomment the below if you want to cite something...

% \begin{thebibliography}{99999999}                                                                                         

% \bibitem[Grinbe17]{nogra}Darij Grinberg, \textit{Notes on graph theory},
% draft of two chapters,
% 4th April 2022.\newline
% \url{https://www.cip.ifi.lmu.de/~grinberg/t/17s/nogra.pdf}

% \end{thebibliography}

\end{document}

