% 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{\bidir}{\operatorname{bidir}}
\newcommand{\conn}{\operatorname{conn}}
\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{\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{\scalp}[1]{\left< #1 \right>}
% $\scalp{...}$ compiles to <...> (scalar product).
\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}{9} % 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 2025: \\
Homework \psetnumber\\% The assignment title
due 2025-06-07 at 11:59 PM \\
\textbf{Please solve 3 of the 9 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 strongly connected
multidigraph.

A \emph{wealth distribution} on $D$ shall mean a
family $\tup{k_v}_{v \in V}$ of integers (one for
each vertex $v \in V$).
If $k = \tup{k_v}_{v \in V}$ is a wealth
distribution, then we refer to each value $k_v$ as
the \emph{wealth} of the vertex $v$, and we define
the \emph{total wealth} of $k$ to be the sum
$\sum_{v \in V} k_v$.
We say that a vertex $v$ is \emph{in debt} in a
given wealth distribution $k = \tup{k_v}_{v \in V}$
if its wealth $k_v$ is negative.

For any vertices $v$ and $w$, we let $a_{v,w}$
denote the number of arcs that have source $v$
and $w$.

A \emph{donation} is an operation that
transforms a wealth distribution as follows:
We choose a vertex $v$, and we decrease its
wealth by its outdegree $\deg^+ v$, and then
increase the wealth of each vertex $w \in V$
(including $v$ itself) by $a_{v,w}$.
(You can think of $v$ as donating a unit of
wealth for each arc that has source $v$. This
unit flows to the target to this arc.
Note that a donation does not change the
total wealth.)

Let $k$ be a wealth distribution on $D$ whose
total wealth is larger than $\abs{A} - \abs{V}$.
Prove that by an appropriately chosen finite
sequence of donations, we can ensure that no
vertex is in debt.

\subsection{Remark}

For instance, consider the digraph
\[
\begin{tikzpicture}[scale=1]
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(A) at (0:2) {$1$};
\node(B) at (60:2) {$2$};
\node(C) at (120:2) {$3$};
\node(D) at (180:2) {$4$};
\node(E) at (240:2) {$5$};
\node(F) at (300:2) {$6$};
\end{scope}
\begin{scope}[every edge/.style={draw=black,very thick}]
\path[->] (A) edge (B) (B) edge (C) (D);
\path[->] (C) edge (D) edge (F) (D) edge (E) (E) edge (A);
\path[->] (F) edge (A);
\end{scope}
\end{tikzpicture}%
\]
with wealth distribution
$\tup{k_1, k_2, k_3, k_4, k_5, k_6}
= \tup{-1, -1, 1, 2, 0, 1}$.
The vertices $1$ and $2$ are in debt here, but
it is possible to get all vertices out of debt
by having the vertices $4, 5, 6, 1$ donate in
some order (the order clearly does not matter
for the result\footnote{Depending on the order,
some vertices will go into debt in the process,
but this is okay as long as they ultimately
end up debt-free.}).

Note that vertices are allowed to donate multiple
times (although in the above example, this was
unnecessary).

\subsection{Hint}

Show first that if the total wealth is larger
than $\abs{A} - \abs{V}$, then at least one
vertex $v$ has wealth $\geq \deg^+ v$.

\subsection{Solution}

...

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

\section{Exercise 2}

\subsection{Problem}

We continue with the setting and terminology
of Exercise 1.

A \emph{clawback} is an operation that
transforms a wealth distribution as follows:
We choose a vertex $v$, and we increase its
wealth by its outdegree $\deg^+ v$, and then
decrease the wealth of each vertex $w \in V$
(including $v$ itself) by $a_{v,w}$.
(Thus, a clawback is the inverse of a
donation.)

Let $k$ be a wealth distribution on $D$ whose
total wealth is larger than $\abs{A} - \abs{V}$.
Prove that by an appropriately chosen finite
sequence of clawbacks, we can ensure that no
vertex is in debt.

\subsection{Remark}

Note that we are still assuming $D$ to be
strongly connected.
Otherwise, the truth of the claim is not
guaranteed.
For instance, for the digraph
\[
\begin{tikzpicture}[scale=1.4]
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(1) at (0, 0) {$1$};
\node(2) at (1, 0) {$2$};
\node(3) at (0, 1) {$3$};
\node(4) at (1, 1) {$4$};
\end{scope}
\begin{scope}[every edge/.style={draw=black,very thick}, every loop/.style={}]
\path[->] (1) edge (3) edge (4) (2) edge (3) edge (4);
\end{scope}
\end{tikzpicture}
\]
with wealth distribution
$\tup{k_1, k_2, k_3, k_4} = \tup{0, 0, -1, 2}$,
no sequence of donations and clawbacks will
result in every vertex being out of debt
(since the wealth difference $k_4 - k_3$ is
preserved under any donation or clawback, but this
difference is too large to come from a debt-free
distribution with total weight $1$).

\subsection{Hint}

Show that any donation is equivalent to an
appropriately chosen composition of clawbacks.

\subsection{Solution}

...

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

\section{Exercise 3}

\subsection{Problem}

Let $X$ and $Y$ be two finite sets such that
$\abs{X} \leq \abs{Y}$.
Let $f : X \to Y$ be a map that is not constant.
(A map is said to be \emph{constant} if all its
values are equal.)
Prove that there exists an injective map $g : X \to Y$
such that each $x \in X$ satisfies
$g\tup{x} \neq f\tup{x}$.

\subsection{Solution}

...

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

\section{Exercise 4}

\subsection{Problem}

Let $\tup{G, X, Y}$ be a bipartite graph with
$X \neq \varnothing$.
Assume that $G$ has an $X$-complete matching.

An edge $e$ of $G$ will be called \emph{useless}
if $G$ has no $X$-complete matching that contains $e$.

Prove that there exists a vertex $x \in X$ such that
no edge that contains $x$ is useless.

\subsection{Solution}

...

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

\section{Exercise 5}

\subsection{Problem}

Let $G = \tup{V, E, \varphi}$ be a multigraph.
Let $M$ be a matching of $G$.

An \emph{augmenting path} for $M$ shall mean a path
$\tup{v_0, e_1, v_1, e_2, v_2, \ldots, e_k, v_k}$ of
$G$ such that $k$ is odd\footnote{Note that $k = 1$
is allowed.} and such that
\begin{itemize}
\item the even-indexed edges $e_2, e_4, \ldots, e_{k-1}$
      belong to $M$ (note that this condition is
      vacuously true if $k = 1$);
\item the odd-indexed edges $e_1, e_3, \ldots, e_k$
      belong to $E \setminus M$;
\item neither the starting point $v_0$ nor the
      ending point $v_k$ is matched in $M$.
\end{itemize}

Prove that $M$ has maximum size among all matchings
of $G$ if and only if there exists no augmenting path
for $M$.

\subsection{Hint}

If $M$ and $M'$ are two matchings of $G$, what can you
say about the symmetric difference $\tup{M \cup M'}
\setminus \tup{M \cap M'}$ ?

\subsection{Solution}

...

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

\section{Exercise 6}

\subsection{Problem}

Let $\tup{G, X, Y}$ be a bipartite graph.
Prove that
\[
\sum_{A \subseteq X} \tup{-1}^{\abs{A}} \ive{N\tup{A} = Y}
=
\sum_{B \subseteq Y} \tup{-1}^{\abs{B}} \ive{N\tup{B} = X}
\]
(where we are using the Iverson bracket notation).

\subsection{Solution}

...

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

\section{Exercise 7}

\subsection{Problem}

Let $A$ and $B$ be two finite sets such that
$\abs{B} \geq \abs{A}$.
Let $d_{i,j}$ be a real number for each
$\tup{i, j} \in A \times B$.
Let\footnote{The notation
``$\min_{\text{some kind of objects}} \text{some kind of value}$''
means the minimum of the given value over all objects
of the given kind.
An analogous notation is used for a maximum.}
\[
m_1
= \min\limits_{\sigma : A \to B \text{ injective}}
     \ \max\limits_{i\in A} d_{i,\sigma\tup{i}}
\]
and
\[
m_2
= \max\limits_{\substack{I\subseteq A;\ J\subseteq B;\\
                    \abs{I} + \abs{J} = \abs{B} + 1}}
     \ \min\limits_{\tup{i, j} \in I \times J} d_{i,j} .
\]
Prove that $m_1 = m_2$.

\subsection{Solution}

...

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

\section{Exercise 8}

\subsection{Problem}

Let $c$ and $r$ be two positive integers.
Let $T$ be a tournament with more than $r^c$ vertices.
Each arc of $T$ is colored with one of the $c$
colors $1, 2, \ldots, c$.
Prove that $T$ has a monochromatic path of length $r$.

(A path is said to be \emph{monochromatic} if all its
arcs have the same color.)

\subsection{Hint}

Induct on $c$, and apply Gallai-Milgram to a certain
digraph in the induction step.
(Note that the case $c = 1$ recovers the Easy Redei
Theorem.)

\subsection{Solution}

...

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

\section{Exercise 9}

\subsection{Problem}

Let $D$ be a balanced multidigraph.
Let $s$ and $t$ be two vertices of $D$.
Let $k \in \NN$.
Assume that $D$ has $k$ pairwise arc-disjoint paths from $s$ to $t$.
Show that $D$ has $k$ pairwise arc-disjoint paths from $t$ to $s$.

[We say that $k$ paths $\mathbf{p}_1,\ \mathbf{p}_2,\ \ldots,
\ \mathbf{p}_k$ are \emph{pairwise arc-disjoint} if and only if
no arc appears in more than one of these $k$ paths.]

\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}

