# HG changeset patch
# User Madarasi Peter
# Date 1479932126 -3600
# Node ID d35847f1417843e13743ec03c6041799362424be
# Parent  e73184c3928f4ec78735a2bdeb173c71d5ea290f
All proofs of vf2pp' section removed

diff -r e73184c3928f -r d35847f14178 damecco.tex
--- a/damecco.tex	Wed Nov 23 20:59:40 2016 +0100
+++ b/damecco.tex	Wed Nov 23 21:15:26 2016 +0100
@@ -730,25 +730,6 @@
 view of the matching procedure, this means, that always the same node
 of $G_{small}$ will be covered on the d-th level.
 \end{claim}
-\begin{proof}
-In order to make the search space a tree, the pairs in $\{(u,v)\in
-P(s) : \exists \hat{u} : \hat{u}\prec u\}$ are excluded from $P(s)$.
-\newline
-Let $\tilde{P}(s):=P(s)\backslash \{(u,v)\in P(s) : \exists \hat{u} :
-\hat{u}\prec u\}$
-\newline
-The relation $\prec$ is a total ordering, so $\exists!\ \tilde{u} :
-\forall\ (u,v)\in \tilde{P}(s): u=\tilde u$. Since a pair form
-$\tilde{P}(s)$ is chosen for including into $M(s)$, it is obvious,
-that only $\tilde{u}$ can be covered in $V_{small}$. Actually,
-$\tilde{u}$ is the smallest element in $T_{small}(s)$ (or in
-$V_{small}\backslash M_{small}(s)$, if $T_{small}(s)$ were empty), and
-$T_{small}(s)$ depends only on the covered nodes of $G_{small}$.
-\newline
-Simple induction on $d$ shows that the set of covered nodes of
-$G_{small}$ is unique, if $d$ is given, so $\tilde{u}$ is unique if
-$d$ is given.
-\end{proof}
 
 \begin{definition}
 An order $(u_{\sigma(1)},u_{\sigma(2)},..,u_{\sigma(|V_{small}|)})$ of
@@ -772,29 +753,6 @@
 (u_{\sigma{(k)}},u_{\sigma{(i)}})\in E'_{small}$, where $i,j,k,l\in
 \{1,..,|V_{small}|\}$\newline
 \end{claim}
-\begin{proof}
-Suppose a matching order is given. It has to be shown that the node
-sequence has a structure described above.\\ Let
-$G'_{small}=(V'_{small},E'_{small})$ be an arbitrary component and $i$
-an arbitrary index.
-\newline
-$(\exists j : j<i\wedge u_{\sigma(j)},u_{\sigma(i)}\in
-V'_{small})\Rightarrow u_{\sigma(i)}$ is not the first covered node in
-$G_{small}\ \Rightarrow u_{\sigma(i)}$ is connected to a covered node
-$u_{\sigma(k)}$ where $k<i$, since $u_{\sigma(i)}\in T_{small}(s)$ for
-some $s$ and $T_{small}(s)\subseteq{V'_{small}}$ contains only nodes
-connected to at least one covered node. It's easy to see, that
-$\forall l: k\leq l\leq i \Rightarrow u_{l}\in V'_{small}$, since
-$T_{small}(s)$ contains only nodes connected to some covered ones,
-while it is not empty, but if it were empty, then $u_{\sigma(k)}$ and
-$u_{\sigma(i)}$ were not in the same component.
-
-Now, let us show that if a node sequence has the special structure
-described above, it has to be matching
-order.\\ $(u_{\sigma(1)},u_{\sigma(2)},..,u_{\sigma(|V_{small}|)})$ is
-a total ordering, which determines the matching order
-$(u_{\sigma(1)},u_{\sigma(2)},..,u_{\sigma(|V_{small}|)})$.
-\end{proof}
 
 To summing up, a total ordering always uniquely determines a matching
 order, and every matching order can be determined by a total ordering,
@@ -964,32 +922,6 @@
 \begin{claim}
 \[LabCut_{IND}((u,v),M(s))\!:=\!\!\!\!\!\bigvee_{l\ is\ label}\!\!\!\!\!\!\!|\Gamma_{large}^{l} (v) \cap T_{large}(s)|\!<\!|\Gamma_{small}^{l}(u)\cap T_{small}(s)|\ \vee\]\[\bigvee_{l\ is\ label} \newline |\Gamma_{large}^{l}(v)\cap \tilde{T}_{large}(s)| < |\Gamma_{small}^{l}(u)\cap \tilde{T}_{small}(s)|\] is a cutting function by IND.
 \end{claim}
-\begin{proof}
-It has to be shown, that $LabCut_{IND}((u,v),M(s))=true\Rightarrow$
-the mapping can not be extended to a whole
-mapping.\\ $LabCut_{IND}((u,v),M(s))=true,$ iff the following
-holds. $\\\exists l: |\Gamma_{large}^{l} (v)\ \cap\ T_{large}(s)| <
-|\Gamma_{small}^{l} (u)\ \cap\ T_{small}(s)| \vee
-|\Gamma_{large}^{l}(v)\cap \tilde{T}_{large}(s)| <
-|\Gamma_{small}^{l}(u)\cap \tilde{T}_{small}(s)|$.
-
-Suppose that $|\Gamma_{large}^{l} (v)\ \cap\ T_{large}(s)| <
-|\Gamma_{small}^{l} (u)\ \cap\ T_{small}(s)|$. Each node of
-$\Gamma_{small}^{l} (u)\ \cap\ T_{small}(s)$ has to be matched to a
-node in $\Gamma_{large}^{l} (v)\ \cap\ T_{large}(s)$, so
-$\Gamma_{large}^{l} (v)\ \cap\ T_{large}(s)$ can not be smaller than
-$\Gamma_{small}^{l} (u)\ \cap\ T_{small}(s)$. That is why $M(s)$ can
-not be extended to a whole mapping.
-
-Otherwise $|\Gamma_{large}^{l}(v)\cap \tilde{T}_{large}(s)| <
-|\Gamma_{small}^{l}(u)\cap \tilde{T}_{small}(s)|$ has to be
-true. Similarly, each node of $\Gamma_{large}^{l}(v)\cap
-\tilde{T}_{large}(s)$ has to be matched to a node in
-$\Gamma_{small}^{l}(u)\cap \tilde{T}_{small}(s)$,
-i.e. $\Gamma_{large}^{l}(v)\cap \tilde{T}_{large}(s)$ can not be
-smaller than $\Gamma_{small}^{l}(u)\cap \tilde{T}_{small}(s)$, if
-$M(s)$ is extendible.
-\end{proof}
 The following claims can be proven similarly.
 \subsubsection{Graph isomorphism}
 \begin{claim}
@@ -1338,7 +1270,7 @@
 
 
 
-\begin{figure}[H]
+\begin{figure}
 \vspace*{-1.5cm}
 \hspace*{-1.5cm}
 \begin{subfigure}[b]{0.55\textwidth}
@@ -1472,7 +1404,7 @@
 
 
 
-\begin{figure}[H]
+\begin{figure}
 \vspace*{-1.5cm}
 \hspace*{-1.5cm}
 \begin{subfigure}[b]{0.55\textwidth}