
diff -r 5e8ffb58bdaa -r 81a08931ecb4 handouts/ho06.tex
--- a/handouts/ho06.tex	Sat Nov 08 02:28:30 2014 +0000
+++ b/handouts/ho06.tex	Sat Nov 08 02:51:34 2014 +0000
@@ -203,7 +203,51 @@
 problem at hand.\footnote{The question whether $P = NP$ or not,
 we leave to others to speculate about.} 
 
-One NP problem is the \emph{graph isomorphism problem}.
+One NP problem is the \emph{graph isomorphism problem}. It
+essentially determines whether the following two graphs, say
+$G_1$ and $G_2$, can be moved and stretched so that they look
+exactly the same.
+
+\begin{center}
+\begin{tabular}{c@{\hspace{8mm}}c@{\hspace{8mm}}c}
+$G_1$ & $G_2$\\
+\raisebox{-13mm}{\includegraphics[scale=0.4]{../pics/simple.png}} &
+\raisebox{-13mm}{\includegraphics[scale=0.4]{../pics/simple-b.png}}&
+
+\footnotesize
+\begin{tabular}{rl}
+Graph $G_1$	& Graph $G_2$\\
+a	& 1\\
+b	& 6\\
+c	& 8\\
+d	& 3\\
+g	& 5\\
+h	& 2\\
+i  &  4\\
+j  & 7\\
+\end{tabular}
+\end{tabular}
+\end{center}
+
+\noindent The table on the right gives a mapping of the nodes
+of the first graph to the nodes of the second. With this we
+can check: node $a$ is connected in $G_1$ with $g$, $h$ and
+$i$. Node $a$ maps to node $1$ in $G_2$, which is connected to
+$2$, $4$ and $5$, which again correspond via the mapping. Let
+us write $\sigma$ for such a table and let us write
+
+\[G_1 = \sigma(G_2)\]
+
+\noindent for two isomorphic graphs. It is actually very 
+easy to construct two isomorphic graphs: Start with an
+arbitrary graph, re-label the nodes consistently. What
+Alice need for the protocol below is to generate such 
+isomorphic graphs.
+
+Now the secret which Alice tries to hide is the knowledge of
+such an isomorphism $\sigma$ between two such graphs. But she
+can convince Bob whether she knows such an isomorphism for two
+graphs. 
 
 \subsubsection*{Using Modular Arithmetic for ZKP Protocols}
 




