\documentclass[12pt]{scrartcl}%<<<1

% Package <<<
\usepackage{tikz}
\usepackage{array}
\usepackage{engord}
\usepackage{listings}
\usepackage{titlesec}
\usepackage{fancyhdr}
\usepackage{clrscode}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage[plain]{fancyref}
\usepackage[unicode,colorlinks]{hyperref}
\usepackage{graphicx,tabularx}
\usepackage[shortlabels]{enumitem}
\usepackage[retainorgcmds]{IEEEtrantools}
\usepackage{amsmath,amssymb,amsthm,amscd,amstext}
\usepackage{mathtools}
 
\usepackage{setspace}
\usepackage{lastpage}
\usepackage{extramarks}
\usepackage{chngpage}

\usepackage{lmodern}
\usepackage{mathpazo}
\usepackage{inconsolata}


% >>>

% Theorem environment <<<
\theoremstyle{definition}   \newtheorem{definition}{Definition}[section]
\theoremstyle{plain}        \newtheorem{theorem}{Theorem}[section]
\theoremstyle{plain}        \newtheorem{lemma}[theorem]{Lemma}
\theoremstyle{plain}        \newtheorem{corollary}[theorem]{Corollary}
\newcommand*{\fancyrefdeflabelprefix}{def}
\newcommand*{\fancyrefthmlabelprefix}{thm}
\newcommand*{\fancyreflemlabelprefix}{lem}
\newcommand*{\fancyrefcorlabelprefix}{cor}
\frefformat{plain}{\fancyrefdeflabelprefix}{definition (#1)}
\Frefformat{plain}{\fancyrefdeflabelprefix}{Definition (#1)}
\frefformat{plain}{\fancyrefthmlabelprefix}{theorem (#1)}
\Frefformat{plain}{\fancyrefthmlabelprefix}{Theorem (#1)}
\frefformat{plain}{\fancyreflemlabelprefix}{lemma (#1)}
\Frefformat{plain}{\fancyreflemlabelprefix}{Lemma (#1)}
\frefformat{plain}{\fancyrefcorlabelprefix}{corollary (#1)}
\Frefformat{plain}{\fancyrefcorlabelprefix}{Corollary (#1)}

% >>>

% Mathematics setting <<<
\DeclareMathOperator{\Var}{Var}
\DeclareMathOperator{\E}{E}
\DeclareMathOperator{\Span}{span}
\DeclareMathOperator*{\argmax}{\arg \max}
\DeclareMathOperator*{\argmin}{\arg \min}
\DeclareMathOperator*{\maximize}{maximize}
\DeclareMathOperator*{\minimize}{minimize}
\providecommand{\abs}[1]{\left\lvert{#1}\right\rvert}
\providecommand{\norm}[1]{\left\lVert{#1}\right\rVert}
\providecommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\providecommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\providecommand{\pa}[1]{\left({#1}\right)}
\providecommand{\p}[1]{\left({#1}\right)}
\providecommand{\br}[1]{\left\{#1\right\}}
\providecommand{\ang}[1]{\langle{#1}\rangle}

\providecommand{\suchthat}{\quad \text{such that} \quad}
\providecommand{\T}{\mathrm{T}}
\providecommand{\dx}{\,\mathrm{d}x}
\providecommand{\dy}{\,\mathrm{d}y}
\providecommand{\dz}{\,\mathrm{d}z}
\providecommand{\dt}{\,\mathrm{d}t}
\providecommand{\ds}{\,\mathrm{d}s}

\allowdisplaybreaks[4]

%>>>

% Setup the page format <<<
\pagestyle{fancy}%
\bibliographystyle{plain}

\lhead{\StudentName}%
\chead{\Title}%
\rhead{\firstxmark}%
\lfoot{\lastxmark}%
\cfoot{}%
\rfoot{Page\ \thepage\ of\ \protect\pageref{LastPage}}%

\renewcommand\headrulewidth{.5pt}%
\renewcommand\footrulewidth{.5pt}%
\renewcommand{\arraystretch}{1.2}
\setstretch{1.1}

% >>>

% Homework Environment <<<
\newcommand{\enterProblemHeader}[1]{\nobreak\extramarks{#1}{#1 continued on next page\ldots}\nobreak%
\nobreak\extramarks{#1}{#1 continued on next page\ldots}\nobreak}%
\newcommand{\exitProblemHeader}[1]{\nobreak\extramarks{#1}{#1 continued on next page\ldots}\nobreak%
\nobreak\extramarks{#1}{}\nobreak}%

\newcommand{\homeworkProblemName}{}%
\newcounter{homeworkProblemCounter}%
\newenvironment{homeworkProblem}[1][Problem \arabic{homeworkProblemCounter}]%
{\stepcounter{homeworkProblemCounter}%
  \renewcommand{\homeworkProblemName}{#1}%
  \section{\homeworkProblemName}%
\enterProblemHeader{\homeworkProblemName}}%
{\exitProblemHeader{\homeworkProblemName}}%

\newcommand{\homeworkSectionName}{}%
\newlength{\homeworkSectionLabelLength}{}%
\newenvironment{homeworkSection}[1]%
{% We put this space here to make sure we're not connected to the above.

  \renewcommand{\homeworkSectionName}{#1}%
  \settowidth{\homeworkSectionLabelLength}{\homeworkSectionName}%
  \addtolength{\homeworkSectionLabelLength}{0.25in}%
  \changetext{}{-\homeworkSectionLabelLength}{}{}{}%
  \subsection{\homeworkSectionName}%
\enterProblemHeader{\homeworkProblemName\ [\homeworkSectionName]}}%
{\enterProblemHeader{\homeworkProblemName}%

% We put the blank space above in order to make sure this margin
% change doesn't happen too soon.
\changetext{}{+\homeworkSectionLabelLength}{}{}{}}%

\newcommand{\Answer}{\ \\{\bfseries \sffamily Answer: }}
\newcommand{\Hint}{\ \\{\bfseries \sffamily Hint: }}
\newcommand{\Remark}{\ \\{\bfseries \sffamily Remark: }}
\newcommand{\Acknowledgement}[1]{\ \\{\bfseries \sffamily Acknowledgement:} #1}

% >>>

% Make title <<<
\newcommand{\Class}{Mathematics for Computer Science}
\newcommand{\ClassInstructor}{Andrew C. Yao}
\newcommand{\StudentName}{Yichao Zhou}
\newcommand{\StudentClass}{CST-10}
\newcommand{\StudentNumber}{2011011299}

\title{{\Class:\\ \Title}\\{\large Instructed by {\itshape\ClassInstructor}}\\\normalsize\vspace{0.1in}\small{Due\ on\ \DueDate}}

\author{\textbf{\StudentName}\ \ \StudentClass\ \ \StudentNumber}
% >>>

% Homework Information <<<1
\newcommand{\Title}{Homework 10}
\newcommand{\DueDate}{May 22, 2011}

\begin{document} %<<<1
  \maketitle

  \tikzset{pot/.style={circle, draw=black,minimum size=20pt,inner sep=0, thick}}

  \begin{homeworkProblem}[Problem 10.4.7 on Page 176] %<<<
    Let $G$ be a bipartite graph with the same number of nodes on both sides.
    Suppose that every nonempty subset $A$ on the left has at least $|A|+1$
    neighbors on the right. Prove that each edge of $G$ can be extended to a
    perfect matching of $G$.

    \Answer For each edge $(u,v)$, suppose we use it in the perfect matching.
    Then we just remove this edge and node $u$ and $v$.  Since we remove a
    right-side node, every non-empty subset $A$ on the left has at least $|A|$
    neighbors on the left.  Using the marriage theorem, there exists a perfect
    matching in the sub-graph.  Along with edge $(u, v)$, we know that each
    edge of $G$ can be extended to a perfect matching of $G$.
  \end{homeworkProblem} %>>>

  \begin{homeworkProblem}[Problem 10.4.9 on Page 177] %<<<
    Let $G$ be a bipartite graph with $m$ nodes on both sides. Prove that if
    each node has degree larger than $m/2$, then it has a perfect matching.

    \Answer We use the marriage theorem to proof this statement.  Let $A$ be
    the subset of the left side.

    When $|A| \le \frac n 2$, node set $A$ has at least $\frac n 2$ neighbors on the
    right side according to the condition.  Thus it satisfies the requirement
    of the marriage theorem.

    When $|A| \ge \frac n 2$, each node of the right side must be connected
    with the $A$.  This is because if one node $u$ does not connect with $A$,
    its degree must be less than $m - |A| < \frac n 2$, which contradict with
    the condition in the problem.
  \end{homeworkProblem} %>>>

  \begin{homeworkProblem}[Problem 10.4.12 on Page 178] %<<<
    Draw a graph whose nodes are the $2$-subsets of $\{a, b, c, d, e\}$, and two
    nodes are adjacent if and only if they are disjoint subsets.

    \begin{enumerate}[(a).]
      \item Show that you get the Petersen graph (Figure 7.13).
      \item How many perfect matchings does the Petersen graph have?
    \end{enumerate}

    \Answer
    \begin{enumerate}[(a).]
      \item 
        \begin{figure}[htbp]
          \centering
          \begin{tikzpicture}[style=thick, scale=0.8]
            \foreach \n\m\deg in {ab/ac/0, bc/bd/72, cd/ce/144, de/da/216, ea/eb/288}{
              \node[pot] (\m) at (\deg:1.5) {\m};
              \node[pot] (\n) at (\deg:3.0) {\n};
              \draw (\m) -- (\n);
            }

            \draw (ab) -- (bc) -- (cd) -- (de) -- (ea) -- (ab);

            \draw (bd) -- (da);
            \draw (bd) -- (eb);
            \draw (ac) -- (ce);
            \draw (ac) -- (da);
            \draw (eb) -- (ce);
          \end{tikzpicture}
          \caption{The Petersen graph}
          \label{fig:p3-1}
        \end{figure}

        See \fref{fig:p3-1}.

      \item Six.  We can use five edges which connects the inner part and the
        outer part.  Or we can use two outer edges, two inner edges and one
        edge from the inner part to outer part, and there are five matchings in
        this forms.
    \end{enumerate}
  \end{homeworkProblem} %>>>

  \begin{homeworkProblem}[Problem 10.4.14 on Page 178] %<<<
    Which $2$-regular bipartite graph with $n$ nodes has the largest number
    of perfect matchings?

    \Answer All the $2$-regular bipartite graph is constructed by cycle.  And
    the number of perfect matchings of all kinds of cycles is two.  So we want
    to partition the graph as small as possible.  The minimum size is four.
    The graph consists of $\floor{n / 4}$ cycles and $(n \bmod 4) / 2$ lines.
  \end{homeworkProblem} %>>>

  \begin{homeworkProblem}[Problem 13.4.5 on Page 210] %<<<
    Let $G_n$ be the graph arising from $K_n$ (where $K_n$ is the complete
    graph on $n$ vertices) by omitting the edges of a Hamiltonian cycle.
    Determine the chromatic number of $G_n$. 

    \Answer Consider the Hamiltonian cycle is $1 \rightarrow 2 \rightarrow
    \dots \rightarrow n \rightarrow 1$.

    When $n = 2k$, there is a clique $1 \rightarrow 3 \rightarrow \dots
    \rightarrow n-1 \rightarrow n$.  So the chromatic number must be more than
    $k$.  Also we can find a way to color it in $k$ color: assign the color $i$
    to nodes $2i - 1$ and $2i$.

    When $n = 2k+1$, we can find a clique whose size is $k$.  Consider two
    clique whose size is $k$: $1 \rightarrow 3 \rightarrow \dots \rightarrow n
    - 2$ and $n \rightarrow 3 \rightarrow 5 \rightarrow \dots \rightarrow n -
    2$.  So if the chromatic number of $G_n$ is equal to $k$, node $1$ and node
    $n$ must be colored same.  However, there is another clique: $2 \rightarrow
    4 \rightarrow \dots n-1$, whose size is also $k$.  But all the nodes in
    this clique connect with node $1$ or $n$, which are in the same color!
    This means that $k$ colors are not enough.  So we need $k+1$ color: assign
    color $i \le k$ to nodes $2i - 1$ and $2i$ and color $k+1$ to node $n$.

    In conclusion, the chromatic number should be $\ceil{\frac{n+2} 2}$.
  \end{homeworkProblem} %>>>

  \begin{homeworkProblem}[Problem 13.4.7 on Page 210] %<<<
    If every face of a planar map has an even number of edges, then the graph
    is bipartite.

    \Answer  
    \begin{proof}
      First, we call a cycle simple if all the vertices of it has degree two.
      Then we can see that all the cycle can be decomposed as several simple
      cycle' vector's addition.  The method of decomposition can be described
      as: we walk from any vertex on the cycle and moving until meets a vertex
      $v_1$ which we have already visited.  Then the cycle from $v_1$ to $v_1$
      must be a simple cycle.  Then we continue moving and then visit $v_2$
      that we have already visited \dots We repeat this walking until we back
      to the original vertex, which constructs another simple cycle $v_0$.

      Also we know that if a graph has only even cycle, then it is a
      bipartite.  So now we only need to proof that all the simple cycle has
      even number of edges.

      Each simple cycle can be treated as a ``super face'' in a planar map,
      which contain several connected real faces.  Since every inner edges in
      this super face will be counted twice if we add all the number of edges
      of each real face, the parity will not be changed.  Thus all the simple
      cycle has even number of edges.
    \end{proof}
  \end{homeworkProblem} %>>>

  \begin{homeworkProblem}[Special Problem 1] %<<<
    Let $n \ge 5$ be any integer.  Consider the undirected graph $G_n =
    \p{V_n,E_n}$, where $V_n = \{0,1,2,\dots,n-1\}$, and $E_n$ is the set of
    all pairs $\{i,j\}$ satisfying $i \neq j$ and $(i - j) \bmod n \in \{1, 2,
    -1, -2\}$.  Thus, the degree of each vertex is $4$.

    \begin{enumerate}[(a).]
      \item What is the chromatic number $\chi(G_n)$? (The answer may depend on
        $n$.)
      \item Is $G_n$ a planar graph? (The answer may depend on $n$.)
    \end{enumerate}

    \Answer

    \begin{enumerate}[(a).]
      \item If $n = 5$, $\chi(G_5) = \chi(K_5) = 5$.

        If $n \equiv 0 \pmod 3$, we can use three colors to color all the
        vertices:  vertex $x$ will be assigned color $x \bmod 3$.  We can
        easily verify that no pair of vertices sharing the same edge have the
        same color.

        If $n \equiv 1 \pmod 3$, we can use four colors to color the graph.
        The way is almost as same as when $n \equiv 0 \pmod 3$ except that
        we assign $V_{n-1}$ color $3$.  Also we can not use three colors to
        accomplish the job.  This is because if we assign two different colors
        to vertices $V_1$ and $V_2$, the color of $V_3$ is exclusive since we
        only have three color and $V_3$ is connected with $V_1$ and $V_2$.
        With the same reason, colors of $V_4 \dots V_{n-1}$ are exclusive.  But
        we find that the color of $V_1$ is as same as $V_{n-1}$, which is
        obvious illegal.

        If $n \equiv 2 \pmod 3$, we can also use four color to color the graph.
        We also use the same method as in the first situation to color all the
        vertices except that we give $V_1$ color $4$, $V_{n-1}$ color $3$,
        $V_{n-2}$ color $1$, $V_{n-3}$ color $4$.  The reason why it cannot be
        3-colored is as same as the second situation.

        In conclusion,
        \begin{equation}
          \chi(G_n) =
          \begin{cases}
            3 & n \equiv 0 \pmod 3 \\
            4 & n \equiv 1 \pmod 3 \\
            5 & n \equiv 2 \pmod 3.
          \end{cases}
        \end{equation}

      \item When $n$ is even, $G_n$ is a planar graph.  We can draw it in such
        way:  First we draw $n$ vertices as a regular $n$-gon on a plane.  Then
        we push the vertices that has odd number along the direction of radius
        until they are in the $n/2$-gon constructed by the vertices that has
        even number.  \Fref{fig:sp1b} is the example when $n = 6$.

        \begin{figure}[htbp]
          \centering
          \begin{tikzpicture}[style=thick]
            \foreach \n\deg\r in {0/0/3,1/60/.6,2/120/3,3/180/.6,4/240/3,5/300/.6}
              \node[pot] (\n) at (\deg:\r) {$\n$};
            \foreach \a\b in {0/1,0/5,4/3,4/5,2/1,2/3,1/3,1/5,3/5,2/0,0/4,2/4}
              \draw (\a) -- (\b);
          \end{tikzpicture}
          \caption{Example of (b) when $n = 6$}
          \label{fig:sp1b}
        \end{figure}

        When $n$ is odd, $G_n$ is not a planar graph.  There is a Hamiltonian
        circuit in there graph: $0 \rightarrow 1 \rightarrow \dots \rightarrow
        n-1 \rightarrow 0$.  So this must be a cycle on the planar.  Each edge
        that is not on the cycle must be IN the cycle or OUT the cycle.
        Suppose edge $(0, 2)$ is in the cycle, then $(1, 3)$ must be out the
        cycle because if not, there will be a point of intersection.  If we do
        the same deduction, we can finally get that edge $(n-1, 1)$ must be in
        the cycle.  We also have the edge $(0, 2)$ in the cycle, so it is
        impossible that $G_n$ is a planar graph when $n$ is odd.

        In conclusion, when $n$ is even, $G_n$ is a planar graph.  When $n$ is
        odd, $G_n$ is not a planar graph.
    \end{enumerate}
  \end{homeworkProblem} %>>>

  \Acknowledgement{ %<<<
    Thanks He Pufan \& Feng Qiwei for the help.
  } %>>>

    
  % \bibliography{hw09.bib}
\end{document}
