\documentclass{article} \usepackage[a5paper]{geometry} \usepackage[czech,english]{babel} \usepackage{amssymb,amsmath,amsthm} \usepackage{caption} \usepackage{setspace} \usepackage{ifthen} \usepackage{graphicx} \usepackage{comment} \usepackage{enumerate} \usepackage{color} \usepackage{url} \usepackage{hyperref} \DeclareMathOperator{\clos}{clos} \DeclareMathOperator{\td}{td} \providecommand{\M}{MSO${}_1$ } \newtheorem{theorem}{Theorem}[section] \newtheorem{thm}[theorem]{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{reduction}[theorem]{Reduction} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newcommand\TODO[1]{\textcolor{red}{#1}} \newcommand{\undefine}[1]{\renewcommand{#1}{\error{Command was defined in another paper.}}} \begin{document} \newpage \addcontentsline{toc}{part}{Jitka Novotn\'a} { %enclosed in paranthesis so that definitions/commands of different people do not conflict \setcounter{section}{1} \setcounter{footnote}{0} \setcounter{figure}{0} \setcounter{equation}{0} \setcounter{theorem}{0} \begin{center} \title{Routing} \author{Jitka Novotn\'a} \end{center} \setcounter{section}{0} \TODO{ neco } tabulky jsou pro vrcholy, zaciname hranou rozdelit sekce, kapitoly, zkontrolavat odkazy na zacatku jiny,slozitejsi priklad na nezavisle kostry napr roviny dukaz 5.1 ke konci by to chtelo obrazek Paralelní hrany reccomandet edge nadefinovat? prescribed move?? sjednotit spatne emph see CO~ ref obrazky: definice3 nemám mít ty hrany co nemá definice 2 oznacit i G, H, H1,... goal->destination 3-rez e1->u1 4routin2 oznacit u,v gramatika: resiliency resilient circuit misto circle the cycle atd trail walk path THE first DIRECTED this -> the \section{Introduction} \subsection{Motivation} \subsection{Definitions} We start with some basic definition. \begin{itemize} \item A graph is $k$-edge-connected if it remains connected whenever fewer than $k$ edges are removed. In this text we say just \emph{$k$-connected}. \item An $k$-edge-cut is a set of $k$ edges whose removal produces a subgraph with is not connected. In this text we say just \emph{$k$-cut}. $k$-cut is \emph{minimal} if none of its proper subset is cut. \item \TODO{$G \setminus \{e_1,e_2\dots e_k\}$.} \item \TODO{outdegree} \item \TODO{multigraph} \item \TODO{} \item \TODO{} \end{itemize} Let $G$ be a graph with one vertex marked as \emph{destination}. Unformally, we want to decide whether it is possible to prescribe possible moves from a vertex to its neighborhood such that starting at arbitrary initial vertex we can find a walk to the destination even if some edges were removed. A \emph{switching table} for a vertex $v$ is a table with rows for every neighboring vertex. In the $u$'s row are \emph{recommend} vertices. The first column it is recommend which neighboring vertex of $v$ we should move when we arrived to $v$ from $u$. In the $j$-th column, $j \geq 2$, it is recommend where to move when the edges to previous $j-1$ recommend vertex were removed. You can see an example of switching table for $K_4$ in~Table~\ref{tableK4}. \begin{remark} The switching tables also can recommended from which edge to which edge to move -- i.e. use edges instead vertices and problem still same. \end{remark} \begin{table}\catcode`\-=12 \centering \begin{tabular}{c |c|c|c|} \multicolumn{4}{c}{vertex 1 } \\ \multicolumn{1}{c}{} & \multicolumn{3}{c}{\emph{switching}} \\ \multicolumn{1}{c}{neighbor} & \multicolumn{3}{c}{\emph{table}} \\ \cline{2-4} 0 & 0 & 2 & 3 \\ \cline{2-4} 2 & 0 & 2 & 3 \\ \cline{2-4} 3 & 2 & 3 & 0 \\ \cline{2-4} \end{tabular} \begin{tabular}{c |c|c|c|} \multicolumn{4}{c}{vertex 2 } \\ \multicolumn{1}{c}{} & \multicolumn{3}{c}{\emph{switching}} \\ \multicolumn{1}{c}{neighbor} & \multicolumn{3}{c}{\emph{table}} \\ \cline{2-4} 0 & 0 & 3 & 1 \\ \cline{2-4} 1 & 0 & 3 & 1 \\ \cline{2-4} 3 & 1 & 0 & 3 \\ \cline{2-4} \end{tabular} \begin{tabular}{c |c|c|c|} \multicolumn{4}{c}{vertex 3 } \\ \multicolumn{1}{c}{} & \multicolumn{3}{c}{\emph{switching}} \\ \multicolumn{1}{c}{neighbor} & \multicolumn{3}{c}{\emph{table}} \\ \cline{2-4} 0 & 0 & 2 & 1 \\ \cline{2-4} 1 & 0 & 2 & 1 \\ \cline{2-4} 2 & 0 & 2 & 1 \\ \cline{2-4} \end{tabular} \caption{ The switching tables for $K_4$. (0 is the destination) } \label{tableK4} \end{table} \begin{figure}[h] \centering \includegraphics{imgs/definice1.pdf} \hskip 1cm \includegraphics{imgs/definice2.pdf} \hskip 1cm \includegraphics{imgs/definice3.pdf} \caption{$K_4$; a ragged $K_4$'; a prescribed walk from vertex 1.} \label{definice} \end{figure} For edges $e_1,\ldots,e_k$ of a graph $G$ a \emph{ragged graph} $G'$ is $G \setminus \{e_1,e_2\dots e_k\}$. A \emph{prescribed move} in $G'$ starting at an edge $(u,v)$ is an edge $(v,w)$. Where $w$ is the first vertex in $u$'s row in switching table for $v$ for which the edge $(v,w)$ is in $G$. A \emph{prescribed walk} in $G'$ starting at an edge $(u,v)$ is a walk which use prescribed moves. We say that a graph $G$ has a \emph{$k$-resilient} routing if there are switching tables such that for every ragged graph obtained from $G$ by deleting $k$ edges and for every starting vertex there exists a prescribed walk which reach the destination. A graph $G$ has a \emph{routing} if it has a (mincut$(G)-1$)-routing, i.e. it has a $k$-resilient routing for the largest possible $k$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{2-connected graphs} We show that every 2-connected graphs is 1-resilient i.e. there are switching tables for which prescribed walk reach destination even if one edge was removed. We start by the well known lemma. \begin{lemma}[Ear decomposition of edge 2-connected graph] A graph is 2-connected if and only if it can by created is such way. We choose arbitrary cycle in this graph. Then we iteratively add paths between two vertices or cycle connecting one vertex. \end{lemma} \begin{proof} A graph created in such way is 2-connected because we cannot create a bridge. We can, show how to create a given 2-connected graph $G$ using this construction. Let $G_0$ be a \emph{arbitrary} cycle of $G$. A graph $G_i$ is created from $G_{i-1}$ by adding a path of edges of $G \setminus G_i$. Now suppose for a contradiction that we cannot add any path to $G_i$ and $G_i \ne G$. Then we focus on an edge $(u,v), u \in V(G_i), v \in V(G \setminus G_i)$. By definition $G \setminus \{(u,v)\}$ is connected and there is a path between $u$ and $v$ which does not contain an edge $(u,v)$. We can take the part starting at the vertex $v$ and ending when meets vertex of $G_i$. This part together with the edge $(u,v)$ is a path which we can be added to $G_i$. A contradiction. \end{proof} \begin{theorem} Every 2-connected graph $G$ is 1-resilient. \end{theorem} \begin{proof} We prove it by using two \emph{independent spanning trees} $a,b$. By that we mean two directed spanning trees which are rooted in the destination and do not use any edge of $G$ in same direction. We create switching tables for a vertex $v$ in the following way: \begin{itemize} \item If we arrive to $v$ from an edge which is not in $a$ nor $b$, then we recommend an edge of the spanning tree $a$ which leads from $v$ and as a second option we recommend an edge of $b$. \item If we arrive to $v$ from an arbitrary edge of $a$, then we recommend an edge of $a$ and as a second option we recommend an edge of $b$ which leads from $v$. \item If we arrive to $v$ from an arbitrary edge of $b$, then we recommend an edge of $b$ and as a second option we recommend an edge of $a$ which leads from $v$. \end{itemize} Using these tables, we can prescribe a walk which reaches the destination in every ragged graph. We start by using one spanning tree and if we meet a removed edge, then we change to the second spanning tree and subsequently we reach the destination. We prove that there are such spanning trees by induction on the number of added paths. First, we choose a cycle which contains the destination. If $G$ is just a cycle, then its spanning trees are two maximal paths, as you can see in Figure~\ref{2connected}. \begin{figure}[h] \centering \includegraphics[scale=0.8]{imgs/2connected1.pdf} \hskip 1cm \includegraphics[scale=0.8]{imgs/2connected2.pdf} \caption{Spanning trees in circle; induction step} \label{2connected} \end{figure} Suppose that $G$ was created from a graph $H$ by adding a path $P$. Then the destination can not be contained in the path $P$, because the destination lies in the cycle. The graph $H$ contains, using the induction step, two independent spanning trees. The path $P$ also contains two spanning trees similarly to the case for a cycle. We can combine these spanning trees into spanning trees of $G$ as depicted in Figure~\ref{2connected}. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Three independent spanning trees guarantee 2-resiliency} There is a way how to find switching tables using three \emph{independent spanning trees}. Those are three directed spanning trees, which are rooted in the destination, and do not use same edge of $G$ in same direction. We assign red, green and blue color to those trees. You can see an example of independent spanning trees in Figure~\ref{K4}. \begin{theorem} If a graph has three independent spanning trees, then it is 2-resilient. \end{theorem} \begin{proof} Let $G$ be a graph with three independent spanning trees. We show that a prescribed walk reaches the destination even if two arbitrary edge were removed. We create the switching table for a vertex $v$ in the following way: \begin{itemize} \item If we arrive to $v$ from an edge which is not contained in any independent spanning tree, then we continue to a red edge. \item If we arrive to $v$ from an edge which is contained in some of the independent spanning trees, then we continue to an edge of the same independent spanning tree. \item If a recommended edge of the red tree was removed, then we recommend a green edge. \item If a recommended edge of the green tree was removed, then we recommend a blue edge. \item If a recommended edge of the blue tree was removed, then we recommend a red edge. \end{itemize} \begin{figure} \centering \includegraphics[scale=0.7]{imgs/orientace.pdf} \caption{A prescribed walk in a graph with three independent spanning trees.} \label{orientace} \end{figure} \TODO{pojmenovat ty cesty v obrazku a textu} We show that every prescribed walk ends in the destination. Without lost of generality starting edge was red or not contained in any independent spanning tree. If some red edge $e$ on the red path was removed, then the walk continues on a green path. The green path cannot use the edge $e$, because one of its direction is already occupied by the red tree and the other direction could create a green cycle. Either the green path reaches the destination or some green edge $f$ was removed. In the latter case we switch to the blue path. The blue path cannot use an edge $f$ for the same reason as the green path could not use the edge $e$. Blue path either reaches the destination or it uses an edge $e$ in the other orientation then the red path did. In this case we continue on the red path as if the edge $e$ was not removed. The red path the either reaches the destination or an edge $f$. In the second case we continue on the green path and this time we have to reach the destination. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Reductions} \TODO{rozdelit na redukce a lemma} We can prove that every 3-connected graph has three independent spanning trees using so called \emph{reductions}. \paragraph{A reduction use the following idea} If a graph $G$ has some attribute, then we can use it to construct a smaller 3-connected graph $H$ or graphs $H_1$, $H_2$. These reduced graphs have three independent spanning trees using induction. There is only a few possibilities how these trees use some specified subgraph of the graph. For each of these possibilities we construct independent spanning trees for $G$. \paragraph{} In the following chapter we prove that for every graph with more than four vertices we can use at least one reduction. \subsection{Useless edge reduction} A edge $e$ of graph $G$ is \emph{useless} if $G \setminus e$ is 3-connected. \begin{reduction}[Useless edge reduction] If 3-connected graph $G$ have useless edge $e$ then $H = G \setminus e$. \end{reduction} \begin{lemma}[Useless edge lemma] If a graph $G$ contains useless edge $e$ and all smaller 3-connected graphs has 3 independent spanning trees then $G$ also have 3 independent spanning trees. \end{lemma} \begin{proof} $H$ is smaller then $H$ and 3-connected so we can use its spanning trees for $G$. \end{proof} \subsection{Nontrivial k-cut reduction} A $k$-cut is \emph{nontrivial} if it separates more than one vertex. \TODO{odkazuju se na lemma nebo redukci?, obrazek ma byt blizko} \begin{reduction}[$k$-cut reduction] \label{k-cut} Let $G$ be $k$-connected graph with nontrivial $k$-cut composed by edges $(u_i,v_i)$ for $i \in (1 \dots k)$. A $k$-cut divides graph into components. Subgraph $C_1$ is the component which includes the destination and edges $u_i$. Subgraph $C_2$ are the other components. The graph $H_1$ is created from $G$ by a contraction of subgraph $C_2$ into the vertex $p$. The graph $H_2$ is created from $G$ by a contraction of subgraph $C_1$ into the vertex $d$ and mark this vertex as the destination. \end{reduction} \begin{figure} \centering \includegraphics[scale=0.65]{imgs/3rez.pdf} \caption{3-cut reduction} \label{3rez} \end{figure} \begin{lemma}[k-cut lemma] If a $k$-connected graph $G$ has a nontrivial $k$-cut and all smaller $k$-connected graphs have $k$ independent spanning trees, then $G$ also have $k$ independent spanning trees. \end{lemma} \begin{proof} The graphs $H_1, H_2$ are 3-connected, because they were created from a 3-connected graph by a contraction. The graphs $H_1, H_2$ have less edges then $G$ because $k$-cut was nontrivial. Thus $H_1$ and $H_2$ have three independent spanning trees. First, we color oriented edges of $G$ using independent spanning trees of $H_1, H_2$. Then we prove that every colored path ends in the destination i.e. there are no colored cycles. Every vertex will have outdegree 3 so these colors determine independent spanning trees of $G$. Edges in $C_1$ are colored by the same colors as they have in $H_1$. Edges $(u_i,v_i)$ are colored by the same colors as edges $(u_i,p)$ in $H_1$. We rename colors in $H_2$ such that the edges $(d,v_i)$ have the same color as the edges $(u_i,p)$. Remark that, these edges had only one direction colored in $H_2$. To edges in subgraph $C_2$ we assign the same color as they have in $H_2$. We show that from every node $v$ we can use without lost of generality red edges to reach the destination. If $v \in C_2$, then there is a red path from $v$ to $d$ in recolored $H_2$. This path leads to $u_i$ then using red path in $H_1$ to the destination. If $v \in C_1$, then there was a red path in $H_1$. The problem is that this path can include the vertex $p$. In this case the path the edge $(u_i,p)$ which was replaced by it edge $(u_i,v_i)$ and then continue the red path from $v_i$ as described above. \end{proof} \subsection{Odd edge reduction} We call an edge $e=(u,v)$ \emph{odd} if $\deg(u) = 3$ and $\deg(v) \ge 4$. \begin{reduction}[Odd edge reduction] Let $H$ by the graph which is obtained from $G \setminus e$ by replacing a vertex $u$ and two of its adjacent edges by an edge $f$. \end{reduction} \TODO{neni tam trojuhelnik} \begin{figure}[h] \centering \includegraphics{imgs/pravidloHrana.pdf} \caption{Odd edge reduction.} \label{pravidloHrana} \end{figure} \begin{reduction}[Odd edge reduction] If a graph $G$ contains an odd edge and has no nontrivial 3-cut and all smaller graphs has three independent spanning trees, then $G$ also has three independent spanning trees. \end{reduction} \begin{proof} First we show that $H$ is graph not a multigraph. We use independent spanning trees of $H$. We just divide $f$ into two edges and add the edge $e$. We do not have spanning trees yet since the vertex $u$ is not included in all trees. Fortunately, there is enough free edges to add it to them. See Figure~\ref{lichaHrana}. \TODO{rozepsat} \begin{figure}[h] \centering \includegraphics{imgs/lichaHrana.pdf} \caption{Independent spanning trees near an odd edge.} \label{lichaHrana} \end{figure} \end{proof} \subsection{Edge near the destination reduction} \TODO{zde zminit cubic} We call an edge $e=(u,v)$ \emph{near the destination} when $u$ is adjacent with the destination and $v$ is not. Let $H = G \setminus \{e\}$ where vertices $u$, $v$ and their two adjacent edges are replaced by edges $f$, $g$. This operation is called {\emph topological contraction}. \begin{reduction}[Reduction for an edge near the destination] If a cubic 3-connected graph $G$ has an edge $e$ near the destination and the graph $H$ has three independent spanning trees, then $G$ also has three independent spanning trees. \end{reduction} \begin{figure}[h] \centering \includegraphics{imgs/hranaUCile.pdf} \caption{Edge near the destination reduction} \label{hranaUCile} \end{figure} \begin{proof} First we prove that only one spanning tree of $H$ uses the edge $f$ which is adjacent to the destination and exactly two spanning trees of $H$ use the edge $g$. \TODO{tohle cele delat nekde uplne jinde a dady jen zminit ze to plati} The graph $H$ is cubic with $n$ vertices, so it has $3n/2$ edges. Three of them have just one one possible orientation and the remaining edges have two possible orientations. So there is $3n-3$ possible places for edges of the spanning trees. Each spanning tree uses $n-1$ edges. All three of them thus use $3n-3$ edges, so every possible place is occupied. \TODO{rozepsat} You can see all possible variants of independent spanning trees in $H$ in Figure~\ref{orientaceHrana}. We can extend spanning trees of $H$ into spanning trees for $G$ as it is in Figure~\ref{orientaceHrana}. These are spanning trees because they include all vertices and we did not create a cycle. \begin{figure}[h] \centering \includegraphics{imgs/orientaceHrana.pdf} \caption{Independent spanning trees near the destination.} \label{orientaceHrana} \end{figure} \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{3-connected graphs are 2-resilient} \begin{theorem} Every 3-connected graph $G$ is 2-resilient. \end{theorem} \begin{proof} We prove the statement by induction on the number of edges. \TODO{multihrany} First of all, if the graph has a nontrivial 3-cut, then we use the nontrivial 3-cut reduction. If $G$ contains an edge $e=(u,v)$ such that $\deg(u) \ge 4$ and $\deg(v) \ge 4$, then we define $H = G \setminus e$. If $H$ has a 2-cut $\{f,g\}$, then $\{e,f,g\}$ is a 3-cut in $G$. A set $\{e,f,g\}$ is a nontrivial 3-cut because the vertex in a trivial 3-cut has degree three. The graph $G$ has not a nontrivial 3-cut so $H$ is 3-connected and smaller than $G$ and $e$ is useless edge. $H$ has three independent spanning trees by induction hypothesis and we can use the useless edge reduction. If $G$ contains an odd edge, then we define a smaller graph $H$ as in odd edge reduction. The graph $H$ is 3-connected from a similar reason as in the previous case. If $H$ has a 2-cut $\{f,g\}$, then $\{e,f,g\}$ is a 3-cut in $G$. The set $\{e,f,g\}$ is nontrivial 3-cut because the vertex in a trivial 3-cut has degree three and the vertex $v$ has larger degree and the vertex $u$ is not in $H$ and so edges $f,g$ do not incident with $u$. The graph $H$ is 3-connected and smaller than $G$ so it has three independent spanning trees by induction hypothesis and we can use the odd edge reduction. \begin{figure}[h] \centering \includegraphics{imgs/K4.pdf} \hskip 1cm \includegraphics{imgs/K33.pdf} \hskip 2cm \includegraphics{imgs/Cube.pdf} \caption{Independent spanning trees in $K_4$, $K_{3,3}$ and in the cube.} \label{K4} \end{figure} The graph $G$ has to be cubic. If $G = K_4$ or $G = K_{3,3}$ or $G$ is a cube, then it has three independent spanning trees, see Figure~\ref{K4}. We focus on the neighborhood of the destination. The destination is not in a triangle because there is a 3-cut around triangle and if $G \ne K_4$ this 3-cut is nontrivial. \TODO{plati obeznej a pri by si to zaslouzilo vyzdvihnout} We denote as $Y$ the set of three vertices adjacent to the destination and denote as $X$ the set of vertices adjacent to $Y$. There are six edges are between $Y$ and $X$. The size of $X$ is at least two because $G$ is cubic. If $|X| = 2$, then $G$ is isomorphic to $K_{3,3}$. If $|X| = 3$, then $G$ is isomorphic to the cube or there is a nontrivial 3-cut separating the destination, $Y$ and $X$ from the rest of $G$. \TODO{obrazek} Finally, if $|X| \ge 4$ then at least one vertex from $X$ is connected to $Y$ by exactly one edge $e$. We call this \emph{edge near the destination}. Let $H = G \setminus \{e\}$ \TODO{tohle neni uplne pravda, navic je to nadefinovane driv} where the vertices $u$, $v$ and their two adjacent edges are replaced by the edges $f$, $g$. If $H$ has a 2-cut, then at least one edge of them is $f$ or $g$. If not, it is also 2-cut of $G$. The set $\{f,g\}$ is not a 2-cut because otherwise $e$ and two edges which were removed from $G$ would create a nontrivial 3-cut in $G$. If $\{f, h \ne g\}$ \TODO{škarede, rozepsat} is a 2-cut, then $h$ and two edges which were removed from $G$ create a nontrivial 3-cut in $G$. Similarly for the case when $\{h\ne f, g\}$ is a 2-cut. The graph $H$ is 3-connected and smaller than $G$ so it has three independent spanning trees by induction hypothesis and we can use the edge near the destination reduction. \end{proof} \section{4-connected 4-regular graphs have four independent spanning trees} The proof is quite similar to prove that 3-connected has three independent spanning trees. We already prove nontrivial 4-cut reduction, see section~\TODO{redukce/sekce/..}~\ref{k-cut}. Now we can suppose that $G$ has no nontrivial 4-cut. $K_5$ has four independent spanning trees, see Figure~\ref{K5}. Every $G$ other then $K_5$ has an edge $(u,v)$ where $u$ is neighbour of destination and $v$ is not. Graph $G'$ is created from $G$ by splitting $u$ into edges $e,f$. See Figure \ref{notation} for more notation. \TODO{tady to znaceni musim i rozepsat :-(} \TODO{zminit ze e a g muzou mit stejny konec. multihrany?} \TODO{nahradit G' za H} \begin{figure} \centering \includegraphics{imgs/4routing2.eps} \caption{Creating graph $G'$.} \label{notation} \end{figure} \begin{lemma} $G'$ is 4-connected. \end{lemma} \begin{proof} Recall that $G$ has no nontrivial 4-cut. The dispute, assume that $G’$ has 2-cut. Without lost of generality we can assume that 2-cut uses edges which are shown in Table~\ref{2cut}. Each of these correspond to 3-cut or 4-cut in $G$. In every 4-cut two edges contain vertex $v$ so 4-cut is nontrivial. Contradiction. \begin{table} \centering \begin{tabular}{l|l} 2-cut in $G’$ & cut in $G$ \\ \hline $e,f$ & $e_1,e_2,f_1$\\ $e,g$ & $e_1,e_2,g$\\ $f,g$ & $f_1,f_2,g$\\ $e,i$ & $e_1,e_2,i$\\ $f,i$ & $f_1,f_2,i$\\ $g,i$ & $e_1,e_2,g,i$\\ $g,h$ & $e_1,e_2,g,h$\\ $i,j$ & $e_1,e_2,i,j$\\ \end{tabular} \caption{ The 2-cuts in $G'$ and corresponding cuts in $G$. } \label{2cut} \end{table} Now suppose that $G’$ has 3-cut $c_1,c_2,c_3$ which is minimal. We will count sum of degrees of vertices in component $C$ of $G’\setminus{\{c_1,c_2,c_3\}}$. First, we count internal edges and cut --- it is $2 \times (\text{ \# edges in } C) + 3$ which is odd. But $G$ and $G'$ is 4-regular and so it is $4 \times (\text{ \# vertices in } C)$ which is even. Contradiction. \end{proof} $G'$ is 4-regular 4-connected graph smaller than $G$. So it has four independent spanning trees. Without lost of generality spanning trees on edges $e,f$ have color as in Figure~\ref{4routing}. In the same figure are shown how to modified then for $G$. \begin{figure} \centering \includegraphics{imgs/4routing.eps} \caption{Independent spanning trees near destination.} \label{4routing} \end{figure} \section{4-connected graphs} We proved that every 2-connected and 3-connected graph has a routing. We found two, respectively three, independent spanning trees in every 2-connected, 3-connected respectively, graph and proved that they create a routing. \TODO{anglictina} The proofs were very similar so there is question whether we can generalize them. However, it might not be so easy. \TODO{to neni pravda, spis ze nefunguje prime zobecneni nez ze se kostry nedaji pouzit} Even if four independent spanning trees exists in all 4-connected graphs, it is not true that ``four independent spanning trees generate 3-resiliency``. \TODO{Uvozovky} When color has order red, green, blue, black, red \dots and switching tables are created in a similar way as in the 3-connected case and edges $(1,2)$, $(3,4)$ were removed, then the prescribed walk starting on the edge $(4,1)$ creates a cycle on vertices $1,3,2,4,1, \dots$ and never reaches the destination. \begin{figure}[h] \centering \includegraphics{imgs/4souvisle.pdf} \caption{Four independent spanning trees for $K_5$.} \label{K5} \end{figure} However, we found switching tables proving that every planar triangulation graph is 3-resilient. \section{Planar triangulation graph is 3-resilient} \section{redukce stupne 4} Mejme 4-souvisly graf s vrcholy stupnu 4 nebo 5 (5 neni vedle sebe) a bez netrivialniho ctyrcezu. Vrchol v (deg(v)=4) jde rozlozit na dve hrany tak ze vysledny graf je 4-souvisly. Sporem: a b v c d G puvodni graf H $G \setminus v$ $H_1 H a (a,c), (b,d) H_2 H a (a,b), (c,d) H_3 H a (a,d), (b,c)$ L1: $H_i$ jsou presne 3-souvislile. Dukaz Sporem. Kdyby tam byl 2rez tak oddeluje odjelujici jeden nebo dva vrcholy z {a,b,c,d} tak spolu s hranou/hranami do v tvori 3-rez nebo netrivialni 4-rez v G. spor def hezka cesta. vede mezi dvema vrcholy abcd v H a nevyuziva dalsi dva zbyvajici vrcholy. L2: Disjunktni hezke cesty mezi kazdymi dvojicemi z abcd vedou prave 3. pr mezi ab a cd vedou cesty ac, ac, bc dk: kdyby vedli ctyri byl by $H_i$ 4-souvisly a hotove, kdyby vedli pouze ve je $H_i$ 2-souvisle. L: H je preste 3-souvysly DK: cesty z L2 nevyuzivaji ty hrany co H nema. L3: Pro kazde dva vrcholy z abcd existuje hezka cesta. Dukaz sporem. Pro ac neni. Zaroven mezi ac existuji 3 hranove nezavisle cesty. Ty tedy museji vyuzivat vrcholy bd. Existuji az na izomorfizmus 2 zpusoby jak mohou vest: abc, adc, abdc -> tam je $H_1$ 4-souvisle a abc,adc,adc. v tomto pripade se podivam na rezy v $H_1, H_2$ takove ze rezaji ty cesty. Dvve hrany oddeluji a. Dukaz obrazkem, nic tam nemuze vest jinak by tamto nebyli 3-rezy v $H_1,H_2$ Graf sednoceni hezkych cest pro vsech sest moznych dvojice nazveme P. L4: Existuje P takove ze vsechny cesty v nem jsou hranove nezavisle. Dk: Sporem, vezmeme takove P ze obsahuje nejmensi mozny pocet hran ktere cesty sdileji. Hranu e vyuzivaji buno cesty ab,ac. potom e spolu s prvni hranou cesty ad tvori 2-rez v P oddelujici a. H je trisouvisle takze po odlelani tech dvou hran v nem existuje cesta z a do druhe pulky P. pridame do P tuhle cestu a odebere kousek???? -> mensi protipriklad. mezi ab, cd existuje 4 hranove nezavisle cesty -> spor %\section{Acknowledgment} } \end{document}