% 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{\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{\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}{5} % 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-04 at 11:00 AM \\
\textbf{Please solve 3 of the 6 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.

For two vertices $u$ and $v$ of $D$, we shall write
$u \overset{*}{\to} v$ if there exists a path from $u$
to $v$.

A \emph{root} of $D$ means a vertex $u \in V$ such that
each vertex $v \in V$ satisfies $u \overset{*}{\to} v$.

A \emph{common ancestor} of two vertices $u$ and $v$
means a vertex $w \in V$ such that $w \overset{*}{\to} u$
and $w \overset{*}{\to} v$.

Assume that $D$ has at least one vertex.
Prove that $D$ has a root if and only if every two
vertices in $D$ have a common ancestor.

\subsection{Solution}

...

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

\section{Exercise 2}

\subsection{Problem}

Let $G$ be a multigraph that has no loops.
Assume that there exists a vertex $u$ of $G$ such
that
\[
\text{for each vertex $v$ of $G$, there is a
\textbf{unique} path from $u$ to $v$ in $G$.}
\]
Prove that $G$ is a tree.

\subsection{Remark}

Notice the quantifiers used here:
$\exists u \forall v$.
This differs from the $\forall u \forall v$ in
Statement T2 of the tree equivalence theorem
(Theorem 1.2.4 in
\href{https://www.cip.ifi.lmu.de/~grinberg/t/22s/lec13.pdf}{Lecture 13}).

\subsection{Solution}

...

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

\section{Exercise 3}

\subsection{Problem}

Let $F$ be any field\footnote{If you find it more convenient,
you can assume that $F = \RR$ or $F = \CC$.}.

Let $G = \tup{V, E, \varphi}$ be a multigraph,
where $V = \set{1, 2, \ldots, n}$ for some
$n \in \NN$.

For each edge $e \in E$, we construct a column vector
$\chi_e \in F^n$ (that is, a column vector with $n$
entries) as follows:
\begin{itemize}
\item If $e$ is a loop, then we let $\chi_e$ be the
zero vector.
\item Otherwise, we let $u$ and $v$ be the two
endpoints of $e$, and we let $\chi_e$ be the column
vector that has a $1$ in its $u$-th position, a
$-1$ in its $v$-th position, and $0$s in all other
positions.
(This depends on which endpoint we call $u$ and which
endpoint we call $v$, but we just make some choice and
stick with it. The result will be true no matter how
we choose.)
\end{itemize}

Let $M$ be the $n \times \abs{E}$-matrix over $F$
whose columns are the column vectors $\chi_e$ for all
$e \in E$ (we order them in some way; the exact order
doesn't matter). Prove that
\[
\rank M = \abs{V} - \conn G .
\]
(Recall that $\conn G$ denotes the number of components
of $G$.)

\subsection{Remark}

Here is an example:
Let $G$ be the multigraph
\[
\begin{tikzpicture}[scale=2]
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(1) at (-1,0) {$1$};
\node(2) at (0,0.5) {$2$};
\node(3) at (1,0.5) {$3$};
\node(4) at (1,-0.5) {$4$};
\node(5) at (0,-0.5) {$5$};
\end{scope}
\begin{scope}[every edge/.style={draw=black,very thick}, every loop/.style={}]
\path[-] (1) edge node[above] {$a$} (2);
\path[-] (1) edge node[below] {$c$} (5);
\path[-] (2) edge node[left] {$b$} (5);
\path[-] (2) edge node[above] {$e$} (3);
\path[-] (3) edge node[left] {$d$} (5);
\path[-] (4) edge node[below] {$f$} (5);
\path[-] (3) edge node[right] {$g$} (4);
\path[-] (4) edge[loop right] node[right] {$h$} (4);
\end{scope}
\end{tikzpicture}
\]
(so that $n = 5$).
Then, if we choose the endpoints of $b$ to be $2$ and $5$
in this order, then we have $\chi_b = \begin{pmatrix}
0 \\ 1 \\ 0 \\ 0 \\ -1 \end{pmatrix}$. (Choosing them to
be $5$ and $2$ instead, we would obtain
$\chi_b = \begin{pmatrix}
0 \\ -1 \\ 0 \\ 0 \\ 1 \end{pmatrix}$.)
If we do the same for all edges of $G$ (that is,
we choose the smaller endpoint as $u$ and the larger
endpoint as $v$), and if we order the columns so that
they correspond to the edges
$a,b,c,d,e,f,g,h$ from left to right, then the matrix
$M$ comes out as follows:
\[
M =
\begin{pmatrix}
1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
-1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & -1 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & -1 & 0 \\
0 & -1 & -1 & -1 & 0 & -1 & 0 & 0
\end{pmatrix} .
\]
It is easy to see that $\rank M = 4$, which is
precisely $\abs{V} - \conn G$.

Another way of putting the claim of the exercise
is that the span of the vectors $\chi_e$ for all
$e \in E$ has dimension $\abs{V} - \conn G$.

Topologists will recognize the matrix $M$ as (a
matrix that represents) the boundary operator
$\partial : C_1\tup{G} \to C_0\tup{G}$, where $G$
is viewed as a CW-complex.

\subsection{Solution}

...

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

\section{Exercise 4}

\subsection{Problem}

Let $G = \tup{V, E, \varphi}$ be a connected
multigraph such that $\abs{E} \geq \abs{V}$.
Show that there exists an injective map
$f : V \to E$ such that for each vertex $v \in V$,
the edge $f\tup{v}$ contains $v$.

(In other words, show that we can assign to each
vertex an edge that contains this vertex in such
a way that no edge is assigned twice.)

\subsection{Solution}

...

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

\section{Exercise 5}

\subsection{Problem}

Let $G$ be a connected multigraph.
Let $\mathcal{S}$ be the simple graph whose vertices are
the spanning trees of $G$, and whose edges are defined
as follows:
Two spanning trees $T_1$ and $T_2$ of $G$ are adjacent
(as vertices of $\mathcal{S}$) if and only if $T_2$ can
be obtained from $T_1$ by removing an edge and adding
another (i.e., if and only if there exist an edge
$e_1$ of $T_1$ and an edge $e_2$ of $T_2$ such that
$e_2 \neq e_1$ and $T_2 \setminus e_2 = T_1 \setminus e_1$).

Prove that the simple graph $\mathcal{S}$ is itself
connected.
(In simpler language: Prove that any spanning tree of $G$
can be transformed into any other spanning tree of $G$ by
a sequence of legal ``remove an edge and add another''
operations, where such an operation is called
\emph{legal} if its result is a spanning tree of $G$.)

\subsection{Remark}

Let $G$ be the following multigraph:
\[
\begin{tikzpicture}[scale=1]
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(1) at (-1,-0.5) {$1$};
\node(2) at (1,-0.5) {$2$};
\node(3) at (0,1) {$3$};
\end{scope}
\begin{scope}[every edge/.style={draw=black,very thick}, every loop/.style={}]
\path[-] (1) edge[bend left=10] node[left] {$a$} (3);
\path[-] (1) edge[bend right=10] node[below] {$c$} (2);
\path[-] (2) edge[bend left=20] node[left] {$b$} (3);
\path[-] (2) edge[bend right=20] node[right] {$d$} (3);
\end{scope}
\end{tikzpicture}
\]
Then, the graph $\mathcal{S}$ looks as follows:
\[
\begin{tikzpicture}[scale=1]
\begin{scope}[every edge/.style={draw=black,very thick}, every loop/.style={}]
\path[-] (-4, 2.5) edge (0, 6) edge (4, 2.5) edge (-3, -2);
\path[-] (0, 6) edge (4, 2.5) edge (-3, -2) edge (3, -2);
\path[-] (4, 2.5) edge (3, -2);
\path[-] (-3, -2) edge (3, -2);
\end{scope}
\filldraw[fill=yellow!50!white] (-4, 2.5) circle (2);
\filldraw[fill=yellow!50!white] (0, 6) circle (2);
\filldraw[fill=yellow!50!white] (4, 2.5) circle (2);
\filldraw[fill=yellow!50!white] (-3, -2) circle (2);
\filldraw[fill=yellow!50!white] (3, -2) circle (2);
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(ab1) at (-5,2) {$1$};
\node(ab2) at (-3,2) {$2$};
\node(ab3) at (-4,3.5) {$3$};
\node(ac1) at (-1,5.5) {$1$};
\node(ac2) at (1,5.5) {$2$};
\node(ac3) at (0,7) {$3$};
\node(ad1) at (3,2) {$1$};
\node(ad2) at (5,2) {$2$};
\node(ad3) at (4,3.5) {$3$};
\node(bc1) at (-4,-2.5) {$1$};
\node(bc2) at (-2,-2.5) {$2$};
\node(bc3) at (-3,-1) {$3$};
\node(cd1) at (2,-2.5) {$1$};
\node(cd2) at (4,-2.5) {$2$};
\node(cd3) at (3,-1) {$3$};
\end{scope}
\begin{scope}[every edge/.style={draw=black,very thick}, every loop/.style={}]
\path[-] (ab1) edge[bend left=10] node[left] {$a$} (ab3);
\path[-] (ac1) edge[bend left=10] node[left] {$a$} (ac3);
\path[-] (ad1) edge[bend left=10] node[left] {$a$} (ad3);
\path[-] (ab2) edge[bend left=20] node[left] {$b$} (ab3);
\path[-] (bc2) edge[bend left=20] node[left] {$b$} (bc3);
\path[-] (ac1) edge[bend right=10] node[below] {$c$} (ac2);
\path[-] (bc1) edge[bend right=10] node[below] {$c$} (bc2);
\path[-] (cd1) edge[bend right=10] node[below] {$c$} (cd2);
\path[-] (ad2) edge[bend right=20] node[right] {$d$} (ad3);
\path[-] (cd2) edge[bend right=20] node[right] {$d$} (cd3);
\end{scope}
\end{tikzpicture}
\]

\subsection{Hint}

You must show that any two spanning trees $T_1$ and $T_2$
are path-connected in $\mathcal{S}$.
Induct on the number of edges of $T_1$ that are not edges
of $T_2$.

\subsection{Solution}

...

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

\section{Exercise 6}

\subsection{Problem}

Let $G = \tup{V, E, \varphi}$ be a connected multigraph.
Let $w : E \to \RR$ be a map that assigns a real number
$w\tup{e}$ to each edge $e$. We shall call this real
number $w\tup{e}$ the \emph{weight} of the edge $e$.

If $H = \tup{W, F, \varphi\mid_F}$ is a subgraph of $G$,
then the \emph{weight} $w\tup{H}$ of $H$ is defined to
be $\sum_{f \in F} w\tup{f}$ (that is, the sum of the
weights of all edges of $H$).

A \emph{$w$-minimum spanning tree} of $G$ means
a spanning tree of $G$ that has the smallest weight among
all spanning trees of $G$.

In Lecture 14, we have seen a way to construct a spanning
tree of $G$ by successively removing non-bridges
until only bridges remain. (A \emph{non-bridge} means an
edge that is not a bridge.)

Now, let us perform this algorithm, but taking care
to choose a non-bridge of largest weight
(among all non-bridges) at each step.
Prove that the result will be a $w$-minimum spanning tree.

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

