\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 
\usepackage{textcomp} % to get \textcent

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query
\renewcommand{\coursecopyrightnames}{Dr.~Radhika~Nagpal}

\begin{document} 
\inclassproblems{4, Fri}                    % !! start the paper

{\it Definition:} The graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ are
{\bf isomorphic} iff there is a bijection $f:V_1 \to V_2$ such that
for all $u,v \in V_1$, the edge $(u,v) \in E_1 \iff (f(u),f(v)) \in
E_2$.


%%%%%%%%%%%%%% Problems %%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
Let $L_n$ be the $n+1$-vertex simple ``line'' graph consisting of a
single simple path of length~$n$.  For example, $L_4$ is shown in the
figure below:

\begin{figure}[h]
\begin{center}
\begin{picture}(80,30)
\put(00,15){\circle*{3}} \put(00,15){\line(1,0){20}}
\put(20,15){\circle*{3}} \put(20,15){\line(1,0){20}}
\put(40,15){\circle*{3}} \put(40,15){\line(1,0){20}}
\put(60,15){\circle*{3}} \put(60,15){\line(1,0){20}}
\put(80,15){\circle*{3}}
\end{picture}
\end{center}

\centerline{The line graph $L_4$}
\end{figure}

Let's say a simple graph has ``two ends'' if it has exactly two
vertices of degree~one, and all its other vertices have degree~two.
In particular, for $n \ge 1$, the graph~$L_n$ has two ends. Consider
the following false theorem.

\paragraph{False theorem:}
Every simple graph with two ends is isomorphic to~$L_n$ for
some~$n~\ge~1$.

\begin{problemparts}
\problempart
Draw a diagram of the smallest simple graph with two ends which is not
isomorphic to any line graph.

%%  What is the smallest $n \ge 1$ such that there is an
%%  $n+1$-vertex simple graph with two ends which is \emph{not} isomorphic
%%  to~$L_n$? \hint See part (d).\brule{2em}

\solution{
\begin{center}
\begin{picture}(80,30)
\put(00,15){\circle*{3}} \put(00,15){\line(1,0){20}}
\put(20,15){\circle*{3}}
\put(40,15){\circle*{3}} \put(40,15){\line(1,0){40}}
\put(60,35){\circle*{3}} \put(40,15){\line(1,1){20}}
\put(80,15){\circle*{3}} \put(80,15){\line(-1,1){20}}
\end{picture}\\
The smallest two-ended graph not isomorphic to any line graph.
\end{center}}

\problempart Explain briefly, but clearly, where the following proof
goes wrong:


\paragraph{False proof:}
We prove by induction on the number, $n \ge 1$, of edges in a simple
graph, that every two-ended graph with $n$ edges is isomorphic
to~$L_n$.

(Base case $n = 1$): A simple graph with one edge can only consist of
the two vertices connected by that edge and some number of vertices
not attached to  any edge, i.e., vertices of degree~zero.  Since a
two-ended graph cannot have vertices of degree~zero, the only
two-ended graph with one edge must consist solely of the two vertices
connected by the edge, which makes it isomorphic to~$L_1$.

(Induction case): Assume that $n \ge 1$ and every two-ended graph with
$n$ edges is isomorphic to~$L_n$.  Now let $G_n$ be any two-ended
graph with $n \ge 1$ edges.  By hypothesis, $G_n$ is isomorphic
to~$L_n$.  Suppose an edge is added to~$G_n$ to form a two-ended
graph~$G_{n+1}$.

Since $G_n$ is isomorphic to~$L_n$, it consists of a simple path of
length~$n$.  The only way to add an edge to the path and preserve
two-endedness is to have that edge go from one end---that is, one of
the degree-one vertices---to a new vertex, lengthening the path by
one.  That is, the resulting $n+1$-edge graph must be a simple path of
length~$n + 1$, so it is isomorphic to~$L_{n+1}$.  Q.E.D.

\solution{
The inductive case is argued in an incorrect way.  The inductive case
must consist of a proof for any $n\ge{1}$ that if $G_{n+1}$ is
two-ended then $G_{n+1}\sim L_{n+1}$ ($A\sim{B}$ is a notation for ``$A$
is isomorphic to $B$''), using the assumption that for every two-ended
$G_n$, $G_n\sim{L_n}$ (alternatively, in strong induction, we can use
an assumption that for every $k$, $1\ge{k}\ge{n}$, if $G_k$ two-ended
then $G_k\sim{L_k}$).  

The false proof above does not argue that at all.  Instead, it states
that if one takes a two-ended $G_n$ which is isomorphic to $L_n$, and
extends it by an edge to form a two-ended $(n+1)$-edge graph $G'$,
then $G'\sim{L_{n+1}}$.  This is true, but to transform this argument
into an inductive proof, one would have to argue that every two-ended
$(n+1)$-edge graph $G_{n+1}$ can be formed in this way, i.e. by adding
another edge to some two-ended graph $G_n$.  However, this cannot be
argued because it is not true.  For example, in the solution to part
(a), we have a two-ended graph $G_4$ which cannot be formed by adding
an edge to some two-ended $G_3$.
}

\newpage
\problempart Here is another argument for the same False Theorem.
Explain exactly where it goes wrong.

\paragraph{False proof 2:}
Same induction hypothesis and base case as in part~(b).

(Induction case): For any $n\geq 1$, let $G_{n+1}$ be any two-ended graph
with $n+1$ edges.  Let $G_n$ be the graph which results from removing one
of the degree-one vertices~$v$ of~$G_{n+1}$ and the edge~$\{v,w\}$
attached to it.  So $G_n$ no longer has the vertex, $v$, of degree~one.
But the degree of $w$ is one less in~$G_n$ than it was in~$G_{n+1}$, so
$G_n$ still has two vertices of degree~one and one fewer vertex of
degree~two.  Therefore $G_n$ is also two-ended.  By induction $G_n$
consists of a simple path of length~$n$.  But $G_{n+1}$ is obtained by
attaching an edge from one end of the path to a vertex~$v$ not on the
path, thereby lengthening the path by one.  So $G_{n+1}$ is isomorphic to
a simple path of length~$n+1$; that is, it is isomorphic to~$L_{n+1}$.
Q.E.D.

\solution{
The claim
\begin{quotation}\noindent
$G_n$ still has two vertices of degree~one and one fewer vertex of
degree~two.
\end{quotation}
is wrong.  The degree of $w$ is one less
in~$G_n$ than it was in~$G_{n+1}$, hence it can be equal to one if it
was two in $G_{n+1}$, but it can also be equal to zero if it was one
in $G_{n+1}$.  The false proof above is wrong because it ignores this
this second possibility.  For example, if we take $G_{n+1}=G_4$ from
the solution to part (a):\\
\begin{center}
\begin{picture}(80,30)
\put(00,15){\circle*{3}} \put(00,15){\line(1,0){20}}
\put(20,15){\circle*{3}}
\put(00,20){w}
\put(20,20){v}
\put(40,15){\circle*{3}} \put(40,15){\line(1,0){40}}
\put(60,35){\circle*{3}} \put(40,15){\line(1,1){20}}
\put(80,15){\circle*{3}} \put(80,15){\line(-1,1){20}}
\end{picture}\\
Graph $G_{n+1}$
\end{center}
We see that if you remove $v$ then $w$ will have degree zero in a
resulting graph $G_n$:
\begin{center}
\begin{picture}(80,30)
\put(00,15){\circle*{3}}
\put(00,20){w}
\put(40,15){\circle*{3}} \put(40,15){\line(1,0){40}}
\put(60,35){\circle*{3}} \put(40,15){\line(1,1){20}}
\put(80,15){\circle*{3}} \put(80,15){\line(-1,1){20}}
\end{picture}\\
Graph $G_{n}$
\end{center}
Obviously, $G_n$ is not two-ended.}


\problempart
Describe how to make a small revision to one of the false proofs above
so that it becomes a correct proof of the theorem ``Every
\emph{connected} simple graph with two ends is isomorphic to~$L_n$ for
some~$n \ge 1$.''

\solution{
The proof in part (c) can be easily fixed if the graphs are connected,
because then the quoted false claim will be true.  Here is an
example of how one could inject into the proof from part (c) an
argument justifying the claim for the case of connected
graphs:
\begin{quotation}
[...But the degree of $w$ is one less in~$G_n$ than it was in~$G_{n+1}$.]
Since $G_{n+1}$ was two-ended, $w$ must be of degree either one or two
in $G_{n+1}$.  However, it cannot be of degree one because then
vertices $v$ and $w$ would be connected only to each other and
disconnected from the rest of the graph, which would contradict the
assumption that $G_{n+1}$ is connected.  Therefore, $w$ must have
degree two in $G_{n+1}$, and hence has degree one in $G_n$.
Hence, [ $G_n$ still has two vertices of degree~one and one fewer
vertex of degree~two.  Therefore...]
\end{quotation}

The false proof in part (b) cannot be easily fixed.  If we tried to
use its structure to prove that all connected two-ended graphs are
linear graphs, we would have to supply the argument that every
connected two-ended graph can be formed by adding an edge to some
connected two-ended graph with one less edge.  To argue that would be
as complicated as the above proof.
}
\end{problemparts}
\end{problem}

%--------------------------------------------------------------

\begin{problem}
Let $G_1$ and $G_2$ be two graphs that are isomorphic to each
other. Argue why if there is a cycle of length $k$ in $G_1$, there
must be a cycle of length $k$ in $G_2$.

\solution{ 

%{\em (TA Notes) (comment out before publishing). Make sure that they
%fully understand the previous problem before moving on to this
%one. This should be simple, just to make sure they understand the
%definition of isomorphism.}

%{\bf ADD/FIX SOLUTION}
From the definition of isomorphism we know that for two vertices $u$
and $v$ $(u,v) \in G_1 \iff (f(u),f(v)) \in G_2$. We select the
vertices $v_1$, $v_2$, ..., $v_k$ on $G_1$ that form a cycle of length
$k$. Since we know that $(v_i,v_{i+1}) \in G_1$ for $1 \leq i < k$ and
$(v_k, v_1) \in G_1$, then $(f(v_i),f(v_{i+1})) \in G_2$ for $1 \leq i < k$ and
$(f(v_k),f(v_1)) \in G_2$. Thus, there is a cycle of length $k$ in
$G_2$.


%Easy to argue from the definition of isomorphism. Basically say there
%is a a cycle a1, a2, a3, .. ak in G1, this means there is an edge from
%a1 to a2, a2 to a3, etc etc.

%If g2 is isomoprhic to g1, then there is a function f that is one to
%one from g1 to g2, that presrve edge comnnections.

%So I can take the vertices f(a1), f(a2), f(a3)...  If ai-ai+1 exist,
%then f(ai)-f(ai+1) must exist therefore the cycle f(a1)...f(ak) exist in
%G2.

}

\end{problem}

%--------------------------------------------------------------
\begin{problem}
Prove that definition 1 implies definition 2.

{\em Definition 1:} A tree is an acyclic graph of $n$ vertices that
has $n-1$ edges.

{\em Definition 2:} A {\em tree} is a connected graph such that $\forall
u,v \in V$, there is a unique path connecting $u$ to $v$.

\solution{ 

%{\em (TA Notes) (comment out before publishing). I changed this to do
%only one way implication. Ask them to write it on the board if they
%get done early with the problems.}

In this solution we will prove that both definitions are equivalent.

In general, when we want to show the equivalence of two definitions,
we must show that if the first definition is met, so is the second,
and vice versa.
\paragraph{$(1)\Longrightarrow (2)$} Suppose that $G$ is an acyclic graph with
$|E|=|V|-1$. We need to demonstrate the following two facts:

\begin{description}
\item[1. There is a unique path connecting any pair of vertices] The
proof is by contradiction. Suppose that there exists a pair of
vertices $(u,v)$ with two distinct paths $p_1$ and $p_2$ connecting
$u$ to $v$. In more ``graphic'' terms, we have
$u\stackrel{p_1}{\leadsto}v$ and $u\stackrel{p_2}{\leadsto}v$. Let
$\stackrel{\leftarrow}{p_2}$ be the \emph{reverse} of path $p_2$
(which takes us from $v$ to $u$). Then
$u\stackrel{p_1}{\leadsto}v\stackrel{\stackrel{\leftarrow}{p_2}}{\leadsto}u$
is a cycle from $u$ back to $u$, which contradicts the fact that $G$
is an acyclic graph. Therefore, we conclude that there exists a
\emph{unique} path between any two pairs of vertices.

\item [2. $G$ is connected]We want to prove that an acyclic graph $G$
with $n$ vertices and $n-1$ edges is connected. The proof is by
induction on the number of vertices of $G$.

\paragraph{Base case:} For $n=1$ and $n=2$ the claim holds, since in
both cases, a graph with $n-1$ edges is connected.
\paragraph{Inductive step:} Assume that the claim is true for all graphs
up to size $n$. Consider an acyclic graph $G$ with $n+1$ vertices and
$n$ edges. At least one of the vertices must have degree $1$ (see note
\footnote{Since there are $n$ edges, the sum of the degrees of the
vertices is $2n$. There are $n+1$ vertices, which means that at least
one vertex must have degree either $0$ or $1$ (if they all had degree
$2$ or more, the sum of the degrees would be $\geq 2n+2$). The
$0$-degree vertex is actually imposible, because the subgraph of $n$
vertices would have $n$ edges, and this would create a cycle (see the
second inductive proof). Therefore, at least one vertex has to have
degree exactly 1. }). Now take that vertex of
degree 1 and remove it, along with the associated edge. The graph $G'$
that remains has $n$ vertices and $n-1$ edges and is connected according
to our induction hypothesis. We then restore the vertex we removed to
get back to $G$ and notice that $G$ must also be connected because the
subgraph $G'$ is connected, and the vertex $v$ we just took out is
connected to the subgraph through its edge.

\end{description}

\paragraph{$(2)\Longrightarrow (1)$}Starting from a graph $G$ that
satisfies the second definition,we want to show that the following two
things must be true:

\begin{description}
\item [1. $G$ is acyclic] We can prove this by conradiction. Suppose
that there is a cycle in $G$, and take any pair $(u,v)$ of vertices in
the cycle. Since we are in a cycle, we know that there's a path $p_1$
connecting $u$ to $v$ and another, different path $p_2$ connecting $v$
to $u$. But then taking path $p_2$ in reverse would take us from $u$
to $v$, which contradicts the assumption that there's a \emph{unique}
path connecting every pair of vertices. Therefore, we conclude that
$G$ must be aclyclic.

\item[2. $G$ has $n-1$ edges]. We know that $G$ is a connected graph
and above we showed that it must also be acyclic. In class we showed
that an acyclic graph with $n$ vertices needs at least $n-1$ edges to
be connected. We now need to prove that it can have \emph{at most}
$n-1$ edges (otherwise, it will not be acyclic).  The proof is by
induction on $n$.
\paragraph{Base case:} For $n=0$ and $n=1$, a connected, acyclic graph
can have at most $n-1$ edges. 
\paragraph{Inductive step:} Assume that all connected, acyclic graphs
with $n$ vertices or less have $\leq n-1$ edges. Consider a connected,
acyclic graph $G$ with $n+1$ vertices. Remove a vertex $v$ along with
all incident edges. This will create $k\geq 1$ connected
components\footnote{the case $k=1$ corresponds to the situation in
which the removal of the vertex leaves us with a connected subgraph
(one piece)}. Each connected component is connected (by definition)
and acyclic (since $G$ was acyclic). Therefore by our induction
hypothesis, the $i$th connected component ($1\leq i\leq k$) can have
at most $|V_i|-1$ edges. Thus the total number of edges will be at
most $n-k$. Now, we bring back the vetex we removed along with all its
incident edges. Notice that since $G$ is acyclic, the vertex cannot be
connected to each component with more than one edges\footnote{If there
were two edges connecting the vertex to a connected component, we
could go from the vertex to the connected component through the first
edge, then find a path to the second connection point [guaranteed to
exist b/c we are in a connected component] and return to the original
vertex through the second edge. This would contradict the assumption
that our original graph was acyclic}. This means that the number of
new edges is at most $k$, which brings our total number of edges to at
most $n-k+k=n$. Thus, the claim holds for $G$ as well.
\end{description}

}
\end{problem}


% \begin{problem}
% Prove that the following two definitions of a tree are equivalent.

% {\em Definition 1:} A tree is an acyclic graph of $n$ vertices that
% has $n-1$ edges.

% {\em Definition 2:} A {\em tree} is a connected graph such that $\forall
% u,v \in V$, there is a unique path connecting $u$ to $v$.

% \solution{Let $G$ be a graph of $n$ vertices such that $\forall u,v
% \in V$, there is a unique path connecting $u$ to $v$.

% First we show that $G$ is acyclic.  Suppose, for the purposes of
% contradiction, that $G$ has a cycle.  Pick two vertices $u$ and $v$ on
% the cycle.  Then there are at least two paths connecting $v$ and $u$,
% contradicting the uniqueness assumption.  So $G$ is acyclic.

% Also we note that the existence of paths between every two vertices
% implies that $G$ is connected.  So $G$ is a connected acyclic graph,
% and from class we know that it has $n-1$ edges.

% Conversely, let $G$ be an acyclic graph with $n$ vertices and $n-1$ edges.
% We know from class that such a graph is connected so there exists at least 
% one path between any two vertices.

% Suppose, for the purposes of contradiction, that there are two
% distinct paths $C$ and $C'$ connecting the vertices $u$ and $v$.
% Starting at $u$ consider the first vertex $u'$ where $C$ differs from
% $C'$ (such a vertex exists because the graphs are distinct).  Also
% consider the first vertex $v'$ where $C$ and $C'$ meet again (such a
% vertex exists because both paths end at $v$).  Then there is a simple
% cycle that starts at $u'$ follows $C$ until it reaches $v'$ and
% returns to $u'$ following $C'$.  This contradicts the acyclicity of
% the graph.  

% }
% \end{problem}

\begin{problem}
An edge of a connected graph is called a {\em cut-edge} if
removing the edge disconnects the graph.

\begin{figure}[h]
\begin{center}
\begin{picture}(120,40)

% top row
% line start/slope/length
\put(00,40){\circle*{3}}  \put(00,40){\line(1,0){40}}
                          \put(00,40){\line(1,-1){20}}
\put(40,40){\circle*{3}}  \put(40,40){\line(1,-1){20}}
                          \put(40,40){\line(-1,-1){20}}
\put(100,40){\circle*{3}} \put(100,40){\line(0,-1){40}}
                          \put(100,40){\line(1,-1){20}}
% second row
\put(20,20){\circle*{3}} \put(20,20){\line(0,-1){20}}
\put(60,20){\circle*{3}} \put(60,20){\line(1,0){60}}
                         \put(60,20){\line(0,-1){20}}
\put(120,20){\circle*{3}} \put(120,20){\line(-1,-1){20}}

% bottom row
\put(20,00){\circle*{3}} \put(20,00){\line(1,0){40}}
\put(60,00){\circle*{3}}
\put(100,00){\circle*{3}}

% put A and B
\put(50,30){A}
\put(75,10){B}

\end{picture}
\end{center}
%%\centerline{The line graph $L_4$}
%%\label{fig:cut}
\end{figure}

\begin{problemparts}
\problempart In the above figure, are either A or B cut-edges? Explain.

\solution{
A is not a cut-edge, B is.

If we remove the edge A the two vertices remain connected because
there is another path between those vertices. If we remove B there is
no path from the end vertices to each other, hence the vertices get
disconnected thus disconnecting the graph.

More succinctly, A is part of a cycle and B is not.
}

\problempart Prove that in an undirected connected graph, an edge $e$
is a cut-edge \emph{if and only if} no simple cycle contains $e$.


\solution{

%{\em (TA Notes) (comment out before publishing). Make sure they
%understand how to prove IFF. Ask them to state (write on the board?)
%both directions of the implication}

\begin{proof}
Since there is an {\em if and only if} we need to prove both sides of
the implication --- that if an edge is part of a simple cycle then it
can not be a cut-edge, and if an edge is not part of a simple cycle
then it must be a cut-edge. We will use both directions of this
implication to prove parts b) and c).

First, we prove that if $e$ is contained in a simple cycle, then $e$
is not a cut-edge.  Since $G$ is connected, there exists a path $P$
between every pair of distinct vertices $u$ and $v$.  We must show
that there still exists a path between $u$ and $v$ after edge $e$ is
removed.  Let $e, e_1, e_2, \ldots, e_n$ be the edges in a simple
cycle containing $e$.  Since the cycle is simple, none of the edges
$e_1, e_2, \ldots, e_n$ are equal to $e$.  Therefore, we can construct
a new path that connects $u$ and $v$, but does not contain edge $e$ by
substituting either $e_1, e_2, \ldots, e_n$ or $e_n, e_{n-1}, \ldots,
e_1$ in place of edge $e$ in the path $P$.This shows that the graph
remains connected after edge $e$ is removed, and so edge $e$ is not a
cut-edge.

Next, we prove that if $e$ is not a cut-edge, then $e$ is contained in
a simple cycle.  We will make use of Theorem 1 on page 469 of Rosen
(p.464 in ed.3), which states that there is a {\em simple} path
between every pair of distinct vertices in a connected graph.  Since
$e$ is not a cut-edge, the graph obtained by removing edge $e$ is
connected.  So by the theorem, there exists a simple path $P$
connecting the endpoints of edge edge $e$ even after edge $e$ is
removed from the graph.  Adjoining edge $e$ to path $P$ gives a simple
cycle containing edge $e$.
\end{proof}
}

\problempart Using the previous part, argue that in a tree every edge
is a cut-edge but in an $n \times n$ mesh no edge is a cut-edge. Why
might this be important?

\solution{

For the tree we can simply state that since a tree is acyclic, every
edge is a cut-edge.

For a mesh, when $n=1$, the claim is trivially true because the mesh
contains no edges. But if $n>1$, every edge is part of a cycle:
consider a horizontal edge between adjacent nodes $a_1, a_2$ on the
same row.  Consider the two nodes $b_1, b_2$ either immediately above
or immediately below $a_1, a_2$.  Then $b_1$ is connected to $b_2$
(adjacent nodes on same row); $a_1$ is connected to $b_1$ and $a_2$ is
connected to $b_2$ (adjacent nodes on same column).  So
$a_1-b_1-b_2-a_2$ forms a cycle. Likewise, every vertical edge is part
of a square cycle.  So every edge is part of a cycle, and hence cannot
be a cut-edge. In fact the non-border edges are part of many cycles.

Cut-edges can be an important concept because they point out weak
points that can cause total failure --- consider the graph of utility
lines or a network of processors in a parallel computer. The more
edges you need to remove in order to disconnect the graph the better.}

\end{problemparts}
\end{problem}

\end{document}


% Let $G$ be a graph of $n$ vertices such that $\forall u,v
% \in V$, there is a unique path connecting $u$ to $v$.

% First we show that $G$ is acyclic.  Suppose, for the purposes of
% contradiction, that $G$ has a cycle.  Pick two vertices $u$ and $v$ on
% the cycle.  Then there are at least two paths connecting $v$ and $u$,
% contradicting the uniqueness assumption.  So $G$ is acyclic.

% Also we note that the existence of paths between every two vertices
% implies that $G$ is connected.  So $G$ is a connected acyclic graph,
% and from class we know that it has $n-1$ edges.

% Conversely, let $G$ be an acyclic graph with $n$ vertices and $n-1$ edges.
% We know from class that such a graph is connected so there exists at least 
% one path between any two vertices.

% Suppose, for the purposes of contradiction, that there are two
% distinct paths $C$ and $C'$ connecting the vertices $u$ and $v$.
% Starting at $u$ consider the first vertex $u'$ where $C$ differs from
% $C'$ (such a vertex exists because the graphs are distinct).  Also
% consider the first vertex $v'$ where $C$ and $C'$ meet again (such a
% vertex exists because both paths end at $v$).  Then there is a simple
% cycle that starts at $u'$ follows $C$ until it reaches $v'$ and
% returns to $u'$ following $C'$.  This contradicts the acyclicity of
% the graph.  


% \begin{problem}
% Let $G$ be a bipartite graph with $n$ vertices and $m$ edges.
% Show that $m \leq n^2 /4$

% \solution{Suppose the parts are of sizes $k$ and $n-k$.  Then the
% maximum number of edges the graph may have is $k(n-k)$.  The maximum
% of the function $f(k) = k(n-k)$ is achieved at $k = n/2$, and has the
% value $f(n/2) = n^2 / 4$.  Therefore, $m \leq n^2 / 4$.  }
% \end{problem}

