% 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}{6} % 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-13 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 $G$ be a connected multigraph with an even
number of vertices.
Prove that there exists a spanning subgraph $H$
of $G$ such that each vertex of $H$ has odd
degree (in $H$).

\subsection{Hint}

The problem can be reduced to the case when $G$ is
a tree (how?).

\subsection{Solution}

...

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

\section{Exercise 2}

\subsection{Problem}

Let $T$ be a tree.
Let $\mathbf{p} = \tup{p_0, *, p_1, *, p_2, \ldots, *, p_m}$
be a longest path of $T$.
(We write asterisks for the edges since we don't need to
name them.)

Prove the following:

\begin{enumerate}

\item[\textbf{(a)}] If $m$ is even, then the only
center of $T$ is $p_{m/2}$.

\item[\textbf{(b)}] If $m$ is odd, then the two
centers of $T$ are $p_{\tup{m-1}/2}$ and
$p_{\tup{m+1}/2}$.

\end{enumerate}

\subsection{Remark}

This result (due to Arthur Cayley in 1875) shows once
again that each tree has exactly one center or
two adjacent centers, and also shows that any two
longest paths of a tree have a common vertex.

\subsection{Solution}

...

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

\section{Exercise 3}

\subsection{Problem}

Let $T$ be a tree.
For any vertex $v$ of $T$, we let $c_v$ denote the
size of the largest component\footnote{%
Note that a component (according to our definition)
is a set of vertices;
thus, its size is the number of vertices in it.}
of the graph $T \setminus v$.
(Recall that $T \setminus v$ is the graph
obtained from $T$ by removing the vertex $v$ and
all edges that contain $v$.)

The vertices $v$ of $T$ that minimize the number $c_v$
are called the \emph{centroids} of $T$.

\begin{enumerate}

\item[\textbf{(a)}] Prove that $T$ has no more than
two centroids, and furthermore, if $T$ has two
centroids, then these two centroids are adjacent.

\item[\textbf{(b)}] Find a tree $T$ such that the
centroid(s) of $T$ are distinct from the center(s)
of $T$.

\end{enumerate}

\subsection{Remark}

Here is an example of a tree $T$, where each vertex
$v$ is labelled with the corresponding number $c_v$:

\[
\begin{tikzpicture}[scale=2]
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(20) at (2,0) {$10$};
\node(10) at (1,0) {$10$};
\node(11) at (1,1) {$8$};
\node(21) at (2,1) {$10$};
\node(12) at (1,2) {$10$};
\node(13) at (1,3) {$10$};
\node(22) at (2,2) {$5$};
\node(32) at (3,2) {$7$};
\node(33) at (3,3) {$9$};
\node(43) at (4,3) {$10$};
\node(42) at (4,2) {$10$};
\end{scope}
\begin{scope}[every edge/.style={draw=black,very thick}, every loop/.style={}]
\path[-] (11) edge (20) edge (10) edge (22);
\path[-] (22) edge (13) edge (12) edge (32);
\path[-] (32) edge (21) edge (42) edge (33);
\path[-] (43) edge (33);
\end{scope}
\end{tikzpicture}
\]

\subsection{Hint}

Part \textbf{(a)} is, of course, an analogue of the
corresponding property of centers that we proved in
Lecture 15. However, I don't think it can be solved
in the same way. (Removing all
leaves of a tree can affect the numbers $c_v$ in
rather unpredictable ways.)
Instead, try to show that any two centroids of $T$ must
be adjacent.

\subsection{Solution}

...

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

\section{Exercise 4}

\subsection{Problem}

Let $D = \tup{V, A, \phi}$ be a multidigraph that has
no cycles\footnote{Recall that cycles in a digraph
have to be directed cycles -- i.e., each arc is
traversed from its source to its target.}.
Let $r \in V$ be some vertex of $D$.
Prove the following:

\begin{enumerate}

\item[\textbf{(a)}] If $\deg^- u > 0$ holds for all
$u \in V \setminus \set{r}$, then $r$ is a from-root of
$D$.

\item[\textbf{(b)}] If $\deg^- u = 1$ holds for all
$u \in V \setminus \set{r}$, then $D$ is an arborescence
rooted from $r$.

\end{enumerate}

\subsection{Solution}

...

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

\section{Exercise 5}

\subsection{Problem}

Let $D = \tup{V, A}$ be a simple digraph that has
no cycles.

If $\mathbf{v} = \tup{v_1, v_2, \ldots, v_n}$ is a
list of vertices of $D$ (not necessarily a walk!),
then a \emph{back-cut} of $\mathbf{v}$ shall mean
an arc $a \in A$ whose source is $v_i$ and whose target
is $v_j$ for some $i, j \in \set{1, 2, \ldots, n}$
satisfying $i > j$.
(Colloquially speaking, a back-cut of $\mathbf{v}$ is
an arc of $D$ that leads from some vertex of $\mathbf{v}$
to some earlier vertex of $\mathbf{v}$.)

A list $\mathbf{v} = \tup{v_1, v_2, \ldots, v_n}$ of
vertices of $D$ is said to be a
\emph{toposort}\footnote{This is short for
``topological sorting''. I don't know where this name
comes from.} of $D$ if it contains each vertex of $D$
exactly once and has no back-cuts.

Prove the following:

\begin{enumerate}

\item[\textbf{(a)}] The digraph $D$ has at least one
toposort.

\item[\textbf{(b)}] If $D$ has only one toposort, then
this toposort is a Hamiltonian path of $D$.

\end{enumerate}

\subsection{Remark}

For example, the digraph
\[
\begin{tikzpicture}[scale=2]
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(1) at (-1,0) {$3$};
\node(2) at (0,0) {$2$};
\node(3) at (0.8,-0.8) {$1$};
\node(4) at (0.8,0.8) {$4$};
\end{scope}
\begin{scope}[every edge/.style={draw=black,very thick}, every loop/.style={}]
\path[->] (1) edge (2) (2) edge (3) edge (4);
\end{scope}
\end{tikzpicture}
\]
has two toposorts: $\tup{3,2,1,4}$ and $\tup{3,2,4,1}$.

\subsection{Solution}

...

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

\section{Exercise 6}

\subsection{Problem}

Let $n$ be a positive integer.
Let $K_{n, 2}$ be the simple graph with vertex set
$\set{1, 2, \ldots, n} \cup \set{-1, -2}$ such that
two vertices of $K_{n, 2}$ are adjacent if and only
if they have opposite signs (i.e., each positive
vertex is adjacent to each negative vertex, but no
two vertices of the same sign are adjacent).
We regard $K_{n, 2}$ as a multigraph in the usual
way.

\begin{enumerate}

\item[\textbf{(a)}] Without using the matrix-tree
theorem, prove that the number of spanning trees
of $K_{n, 2}$ is $n \cdot 2^{n-1}$.

\item[\textbf{(b)}] Let $K'_{n, 2}$ be the graph
obtained by adding a new edge $\set{-1, -2}$
to $K_{n, 2}$. How many spanning trees does
$K'_{n, 2}$ have?

\end{enumerate}

\subsection{Remark}

Here is the graph $K_{n, 2}$ for $n = 5$:
\[
\begin{tikzpicture}[scale=2]
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(-1) at (2.5,-1) {$-1$};
\node(-2) at (1.5,-1) {$-2$};
\node(1) at (0,0) {$1$};
\node(2) at (1,0) {$2$};
\node(3) at (2,0) {$3$};
\node(4) at (3,0) {$4$};
\node(5) at (4,0) {$5$};
\end{scope}
\begin{scope}[every edge/.style={draw=black,very thick}, every loop/.style={}]
\path[-] (-1) edge (1) edge (2) edge (3) edge (4) edge (5);
\path[-] (-2) edge (1) edge (2) edge (3) edge (4) edge (5);
\end{scope}
\end{tikzpicture}
\]
And here is the corresponding graph $K'_{n, 2}$:
\[
\begin{tikzpicture}[scale=2]
\begin{scope}[every node/.style={circle,thick,draw=green!60!black}]
\node(-1) at (2.5,-1) {$-1$};
\node(-2) at (1.5,-1) {$-2$};
\node(1) at (0,0) {$1$};
\node(2) at (1,0) {$2$};
\node(3) at (2,0) {$3$};
\node(4) at (3,0) {$4$};
\node(5) at (4,0) {$5$};
\end{scope}
\begin{scope}[every edge/.style={draw=black,very thick}, every loop/.style={}]
\path[-] (-1) edge (1) edge (2) edge (3) edge (4) edge (5);
\path[-] (-2) edge (-1) edge (1) edge (2) edge (3) edge (4) edge (5);
\end{scope}
\end{tikzpicture}
\]

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

