\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{german}
\usepackage{fullpage}

\newcommand{\ZETTELNUMMER}{12}
\newcommand{\ABGABEDATUM}{10. July 2017, in class.}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Problem~\arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\half}[1]{\frac{#1}{2}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\eps}{\varepsilon}

\DeclareMathOperator{\poly}{poly}
\DeclareMathOperator{\tw}{tw}

\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}

\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER.\@ Problem Set for 

\smallskip
\noindent
\large
\textbf{Advanced Algorithms II}\hfill Spring 2017 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Katharina Klost 

\medskip\hrule

\smallskip
\noindent
\textbf{Due} \ABGABEDATUM


\noindent
This is the penultimate problem set.

\vskip 0.5cm

\begin{description}

\AUFGABE{Tree-width of simple graphs}{10 points}

\begin{enumerate}
\item Let $G = (V, E)$ be a tree with at least two nodes. 
  Show that $\tw(G) = 1$.
\item Let $G = (V, E)$ be a cycle with $n \geq 3$ nodes. 
Show that $\tw(G) = 2$.
\end{enumerate}

\AUFGABE{Properties of tree-width}{10 points}

\begin{enumerate}
\item Let $G = (V, E)$ be a connected graph, and let
$H$ be a subgraph of $G$ (not necessarily induced). 
Show that $\tw(H) \leq \tw(G)$.
\item Let $G = (V, E)$ be a connected graph
with $\tw(G) = 1$. Show that $G$ is a tree.

\emph{Hint}: Use Problem 1(b) and (a).
\end{enumerate}

\AUFGABE{Separators from tree-decompositions}{10 points}

Let $G = (V, E)$ be a connected graph, and let 
$T = (W, F)$ and $(V_w)_{w \in W}$ be a tree-decomposition 
for $G$. Let $f = xy$ be an edge of $T$, and let 
$T_x, T_y$ be the components of $T \setminus f$.
Set $X = \bigcup_{w \in T_x} V_w$ and 
$Y = \bigcup_{w \in T_y} V_w$, and let 
$G_x = G_{\vert X}$ and $G_y = G_{\vert Y}$
be the corresponding induced subgraphs of $G$.

Show that $G_x \setminus (V_x \cap V_y)$ and
$G_y \setminus (V_x \cap V_y)$ have no common
vertices and that there is no edge in $E$ between
them.


\end{description}
\end{document}
