01ZTGA:Kapitola1 10

PDF	[ znovu generovat,	výstup z překladu ]	Kompletní WikiSkriptum včetně všech podkapitol.
PDF Této kapitoly	[ znovu generovat,	výstup z překladu ]	Přeložení pouze této kaptioly.
ZIP			Kompletní zdrojový kód včetně obrázků.
Součásti dokumentu 01ZTGA

součást	akce		poslední editace			soubor
Hlavní dokument	editovat	Hlavní stránka dokumentu 01ZTGA	Karel.brinda	15. 1. 2012	23:45
Řídící stránka	editovat	Definiční stránka dokumentu a vložených obrázků	Admin	7. 9. 2015	13:51
Header	editovat	Hlavičkový soubor	Karel.brinda	15. 1. 2012	12:34	header.tex
Kapitola0	editovat	Úvod	Karel.brinda	15. 1. 2012	12:36	cast0.tex
Kapitola1_1	editovat	Základní pojmy	Karel.brinda	15. 1. 2012	12:46	cast1_kapitola1.tex
Kapitola1_2	editovat	Souvislost	Karel.brinda	15. 1. 2012	12:49	cast1_kapitola2.tex
Kapitola1_3	editovat	Bipartitní grafy	Karel.brinda	15. 1. 2012	12:50	cast1_kapitola3.tex
Kapitola1_4	editovat	Stromy	Kubuondr	5. 1. 2019	09:06	cast1_kapitola4.tex
Kapitola1_5	editovat	Hledání minimální kostry grafu	Karel.brinda	15. 1. 2012	12:51	cast1_kapitola5.tex
Kapitola1_6	editovat	Jednotažky	Karel.brinda	15. 1. 2012	12:53	cast1_kapitola6.tex
Kapitola1_7	editovat	Hamiltonovské kružnice a grafy	Karel.brinda	15. 1. 2012	13:34	cast1_kapitola7.tex
Kapitola1_8	editovat	Párování v grafech	Karel.brinda	15. 1. 2012	13:40	cast1_kapitola8.tex
Kapitola1_9	editovat	Toky v sítích	Karel.brinda	15. 1. 2012	13:44	cast1_kapitola9.tex
Kapitola1_10	editovat	Hranové obarvení grafu	Karel.brinda	15. 1. 2012	13:48	cast1_kapitola10.tex
Kapitola1_11	editovat	Vrcholové obarvení grafu	Karel.brinda	15. 1. 2012	13:52	cast1_kapitola11.tex
Kapitola1_12	editovat	Planární grafy	Karel.brinda	15. 1. 2012	13:56	cast1_kapitola12.tex
Kapitola1_13	editovat	Vlastní čísla adjacenční matice grafu	Karel.brinda	15. 1. 2012	13:57	cast1_kapitola13.tex
Kapitola2_1	editovat	Brouwerova věta o pevném bodě	Karel.brinda	15. 1. 2012	14:11	cast2_kapitola1.tex
Kapitola2_2	editovat	Pravděpodobnostní důkazy v teorii grafů	Karel.brinda	15. 1. 2012	14:12	cast2_kapitola2.tex
Kapitola2_3	editovat	Extremální teorie grafů	Karel.brinda	15. 1. 2012	14:16	cast2_kapitola3.tex
Kapitola2_4	editovat	Ramseyovská čísla	Karel.brinda	15. 1. 2012	14:18	cast2_kapitola4.tex
Kapitola3_1	editovat	Obyčejné mocninné řady	Karel.brinda	15. 1. 2012	14:22	cast3_kapitola1.tex
Kapitola3_2	editovat	Exponenciální generující funkce	Karel.brinda	15. 1. 2012	14:22	cast3_kapitola2.tex
Zdrojový kód

%\wikiskriptum{01ZTGA}
 
\section{Hranové obarvení grafu}
 
\begin{defn}
Nechť $G=(V,E)$ je graf, $k\in\N$. Zobrazení $\varphi:E\mapsto\hat{k}$
nazveme $k$-\textbf{hranové obarvení} grafu $G$ (angl. $k$\emph{-edge
colouring}). $\varphi$ se nazývá \textbf{vlastní} (angl. \emph{proper})
$k$-hranové obarvení grafu $G$, pokud\[
\left(\forall e,f\in E,e\neq f\right)\left(\varphi(e)=\varphi(f)\Rightarrow e\cap f=\emptyset\right),\]
tj. pokud hrany se stejnou barvou nemají společný konec. \textbf{Hranová
barevnost} (angl. \emph{edge chromatic number}) $\chi'(G)$ grafu
$G$ je minimální $k$ takové, že $G$ má vlastní $k$-hranové obarvení.
\end{defn}
\begin{rem*}
$\chi'(G)\geq\Delta(G)$.
\end{rem*}
 
 
\begin{rem*}
$\varphi$ je vlastní $k$-hranové obarvení gafu $G$, právě když
pro každé $i\in\hat{k}$ $\varphi^{-1}(i)$ (všechny vrcholy barvy
$i$) představuje párování.
\end{rem*}
\begin{cor*}
Hranová barevnost grafu $G=(V,E)$ je minimální počet disjunktních
párování, jejichž sjednocením je celé $E$.
\end{cor*}
\begin{notation*}
V důkazech budeme často používat obrat ,,$G$ lze obarvit $k$ barvami{}``.
Máme tím vždy na mysli ,,existuje \emph{vlastní} $k$-hranové obarvení
grafu $G${}``. Stejným způsobem budeme hovořit o grafech i v další
kapitole, zabývající se vrcholovým obarvením.
\end{notation*}
 
\subsection{Problém rozvrhu hodin}
 
\begin{example*}
Uvažujme bipartitní graf $G=(V_{1}\cup V_{2},E)$, kde $V_{1}$ představuje
množinu učitelů a $V_{2}$ množinu kroužků. Z $u\in V_{1}$ vede do
$v\in V_{2}$ $m$ hran, pokud učitel $u$ učí v kroužku $v$ $m$
hodin (např. týdně). Nalezneme obarvení grafu $G$, a potom hrany
stejné barvy, představující párování v $G$, znamenají stejný čas
(hodinu, termín) přednášky. Zatím však neuvažujeme omezení počtem
volných místností.
\end{example*}
\begin{thm}
Je-li $G=(V_{1}\cup V_{2},E)$ bipartitní graf, tak platí $\chi'(G)=\Delta(G)$.
\end{thm}
\begin{notation*}
Vzhledem k velmi častému výskytu symbolu $\Delta(G)$ označujícího
maximální stupeň grafu $G$ v následujícím výkladu budeme místo $\Delta(G)$
psát jen $\Delta$.
\end{notation*}
\begin{proof}
Využijeme důsledku \ref{cor:snatkovy-problem} (sňatkového problému),
který říká, že $r$-regulární bipartitní graf má perfektní párování.
Z $G$ nejdříve takový graf vyrobíme, a to takto:
\begin{enumerate}
\item Nechť BÚNO $\# V_{1}>\# V_{2}$. Potom doplníme do $V_{2}$ potřebný
počet izolovaných vrcholů, vznikne tak $V_{2}'$, $\# V_{1}=\# V_{2}'$.
\item Ve $V_{1}$ vybereme libovolný vrchol $u$ se stupňem $d_{G}(u)<\Delta$.
Potom i ve $V_{2}'$ musí existovat vrchol $v$ se stupňem $d_{G}(v)<\Delta$.
Vrcholy $u,v$ spojíme hranou. Tento krok opakujeme, dokud je to možné,
přičemž skončíme zřejmě právě tehdy, když všechny vrcholy budou mít
stupeň roven $\Delta$.
\end{enumerate}
Dostaneme nový $\Delta$-regulární graf $\tilde{G}=(V_{1}\cup V_{2}',\tilde{E})$.
Najdeme v něm perfektní párování $M$, všechny hrany z $M$ obarvíme
barvou $\Delta$ a následně je z grafu $\tilde{G}$ odstraníme. Tím
získáme ($\Delta-1)$-regulární graf a úvahu můžeme opakovat, dokud
zbývají nějaké hrany. Výsledkem bude, že nakonec původní $\Delta$-regulární
graf $\tilde{G}$ bude obarven $\Delta$ barvami. To znamená, že i
jeho podgraf $G$ lze obarvit $\Delta$ barvami, takže $\chi'(G)\leq\Delta$.
Víme však, že vždy platí $\chi'(G)\geq\Delta$, a tvrzení je tedy
dokázáno.
\end{proof}
\begin{lem}
Nechť $M_{1},M_{2}$ jsou dvě disjunktní párování v grafu $G=(V,E)$
taková, že $\# M_{1}>\# M_{2}$. Potom existují disjunktní párování
$N_{1},N_{2}$ v $G$ taková, že:
\begin{enumerate}
\item $N_{1}\cup N_{2}=M_{1}\cup M_{2},$
\item $\# N_{1}=\# M_{1}-1$, $\# N_{2}=\# M_{2}+1$, tj. $N_{1},N_{2}$
mají menší rozdíl v počtu prvků.
\end{enumerate}
\end{lem}
\begin{proof}
Definujme graf $H=(V,M_{1}\cup M_{2})$. Potom zřejmě $\left(\forall v\in V\right)\left(d_{H}(v)\leq2\right)$.
$H$ je sjednocením izolovaných vrcholů, cest a kružnic sudé délky,
čehož jsme již jednou využili v důkazu Bergeovy věty \ref{thm:bergeova-veta}.
Protože $\# M_{1}>\# M_{2}$, musí v $H$ existovat cesta liché délky
$2k+1$, která má $k$ hran z $M_{2}$ a $k+1$ hran z $M_{1}$. Tuto
cestu označíme $P$. Nyní definujeme\begin{eqnarray*}
N_{1} & = & (M_{1}\backslash P)\cup(P\cap M_{2}),\\
N_{2} & = & (M_{2}\backslash P)\cup(P\cap M_{1}),\end{eqnarray*}
tj. na cestě $P$ vyměníme hrany mezi $M_{1}$ a $M_{2}$, mimo cestu
zařadíme do $N_{i}$ stejné hrany jako jsou v $M_{i}$. $N_{1},N_{2}$
jsou opět párování a přitom si lze snadno rozmyslet, že splňují oba
body dokazovaného lemmatu.
\end{proof}
\begin{example*}
Vraťme se nyní k problému rozvrhu hodin. Nechť $l$ je počet dostupných
místností a $m=\# E$, tj. celkový počet různých vyučovacích hodin
všech kroužků. Potom počet různých časů (termínů, angl. \emph{period})
$P$ potřebných pro výuku musí splňovat $P\geq\left\lceil \frac{m}{l}\right\rceil $.
Rovněž platí $P\geq\Delta$, protože $\Delta=\chi'(G)$, tj. počet
různých barev v nejlepším možném obarvení bipartitního grafu $G$.
Celkově tedy platí\[
P\geq\max\left\{ \left\lceil \frac{m}{l}\right\rceil ,\Delta\right\} .\]
 
 
Předpokládejme, že $l=6$. Snadno si lze představit případ bipartitního
grafu, pro který platí $\Delta=2$ a v němž najdeme jeho hranové obarvení
dvěma barvami, tj. dvě disjunktní párování $M_{1},M_{2}$, pro něž
platí $\# M_{1}=8,\# M_{2}=2$ a $M_{1}\cup M_{2}=E$. Potom počet
potřebných časů pro výuku bude $P=3$, protože blok přednášek $M_{1}$,
které by teoreticky (bez dalších omezení) mohly probíhat současně,
bude nutné rozdělit na dvě části kvůli nedostatku místností. Opakovanou
aplikací minulého lemmatu však lze postupně upravit párování $M_{1},M_{2}$
tak, že $\# M_{1}=\# M_{2}=5$. Potom již bude potřeba pouze $P=2=\max\left\{ \left\lceil \frac{10}{6}\right\rceil ,2\right\} $
různých časů.
 
V následujícím ukážeme, že vždy existuje takový rozvrh, pro nějž platí\[
P=\max\left\{ \left\lceil \frac{m}{l}\right\rceil ,\Delta\right\} .\]
Začneme obecnou úvahou. Nechť existuje $p$ disjunktních párování
$M_{1},...,M_{p}$ v $G$, pro něž platí $\bigcup_{i\in\hat{p}}M_{i}=E$.
Potom opakovaným použitím předchozího lemmatu lze tato párování upravit
tak, že\[
\left(\left(\forall i,j\in\hat{p}\right)\left(\left|\# M_{i}-\# M_{j}\right|\leq1\right)\right),\]
tj. hrany jsou co nejrovnoměrněji rozděleny do jednotlivých párování,
a tak v každém párování je nejvýše $\left\lceil \frac{m}{p}\right\rceil $
hran. V takovém případě je maximální počet hran v párování, tj. číslo
$\max_{i\in\hat{p}}\# M_{i}$, nejmenší možné.
 
Nyní již dokážeme uvedený vztah. Najděme obarvení grafu $G$ $\Delta$
barvami. Potom získáme $\Delta$ disjunktních párování\[
M_{1}=\varphi^{-1}(1),...,M_{\Delta}=\varphi^{-1}(\Delta).\]
 
\begin{enumerate}
\item Nechť $\left\lceil \frac{m}{l}\right\rceil <\Delta$. Potom chceme
dokázat $P=\Delta$. Párování $M_{1},...,M_{\Delta}$ upravíme popsaným
postupem tak, že\[
\left(\forall i\in\hat{\Delta}\right)\left(\# M_{i}\leq\left\lceil \frac{m}{\Delta}\right\rceil \right).\]
Z předpokladu však postupně platí, že\[
\left\lceil \frac{m}{l}\right\rceil <\Delta\Rightarrow\frac{m}{l}<\Delta\Rightarrow\frac{m}{\Delta}<l\Rightarrow\left\lceil \frac{m}{\Delta}\right\rceil \leq l.\]
To znamená, že každé párování $M_{i}$ lze považovat za blok současně
probíhající výuky, protože se vždy vejde do dostupných místností.
Proto $P=\Delta$.
\item Nechť $\left\lceil \frac{m}{l}\right\rceil \geq\Delta$. Potom chceme
dokázat $P=\left\lceil \frac{m}{l}\right\rceil $. Je jasné, že existuje-li
v $G$ $\Delta$ disjunktních párování, pak existuje i $\left\lceil \frac{m}{l}\right\rceil $
disjunktních párování. Stačí totiž potřebný počet párování rozdělit
na dvě nebo více disjunktních párování, nebo definovat $M_{i}=\emptyset$
pro každé $\Delta<i\leq\left\lceil \frac{m}{l}\right\rceil $. Párování
$M_{1},...,M_{\left\lceil \frac{m}{l}\right\rceil }$ pak upravíme
tak, aby\[
\left(\forall i\in\left\{ 1,2,...,\left\lceil \frac{m}{l}\right\rceil \right\} \right)\left(\# M_{i}\leq\left\lceil \frac{m}{\left\lceil \frac{m}{l}\right\rceil }\right\rceil \right).\]
Nyní opět ukážeme, že tato párování už lze brát jako bloky současně
probíhající výuky, protože se vejdou do $l$ místností. Platí totiž:\[
\left\lceil \frac{m}{\left\lceil \frac{m}{l}\right\rceil }\right\rceil \leq\left\lceil \frac{m}{\left(\frac{m}{l}\right)}\right\rceil =\left\lceil l\right\rceil =l.\]
 
\end{enumerate}
\end{example*}
 
\subsection{Vizingova věta}
 
\begin{thm}
\textbf{\emph{\label{thm:Vizing}(Vizing)}}
 
Pro libovolný graf $G$ platí $\chi'(G)\leq\Delta(G)+1$.
\end{thm}
\begin{rem*}
Protože víme $\chi'(G)\geq\Delta$, tak Vizingova věta znamená, že
hranová barevnost grafu může vlastně nabývat jen dvou hodnot: $\Delta$
a $\Delta+1$. Důkaz této věty provedeme až poté, co si připravíme
dvě pomocná tvrzení.
\end{rem*}
\begin{lem}
\label{lem:vizing-lemma-1} Nechť $G=(V,E)$ je souvislý graf, $G$
není kružnice liché délky. Potom existuje $2$-hranové obarvení $G$
takové, že na každém vrcholu se stupněm alespoň $2$ se vyskytují
hrany obou barev.
\end{lem}
\begin{proof}
V důkazu využijeme znalostí o eulerovských grafech.
\begin{enumerate}
\item \label{enu:vizing-lemma-point1}Nechť $G$ je eulerovský. Potom
 
\begin{enumerate}
\item všechny stupně jsou $2$. Z předpokladu se pak jedná o kružnici sudé
délky. Hrany obarvíme střídavě oběma barvami, a každý vrchol pak spojuje
dvě hrany dvou různých barev.
\item existuje vrchol se stupněm $\geq4$. Z tohoto vrcholu pak začneme
eulerovský cyklus, barvíme opět střídavě. Proč zrovna tento vrchol
volíme za počáteční plyne z následujícího. Do každého vrcholu kromě
počátečního totiž vstoupíme po hraně jedné barvy a okamžitě jej opouštíme
po hraně druhé barvy. Pokud bychom za počáteční vrchol zvolili vrchol
se stupněm $2$, tak bychom u něj tuto jistotu neměli. Má-li však
počáteční vrchol stupeň alespoň $4$, potom jím v eulerovském cyklu
projdeme alespoň jednou stejným způsobem jako ostatními vrcholy.
\end{enumerate}
\item Nechť $G$ není eulerovský, tj. podle věty \ref{thm:eulerovske-grafy}
má vrchol s lichým stupněm. Protože ale\[
\sum_{v\in V}d_{G}(v)=2\# E\]
je sudý, je vrcholů s lichým stupněm sudý počet. Když ke grafu $G$
přidáme vrchol $x\notin V$ a napojíme ho na všechny vrcholy s lichým
stupněm, bude mít $x$ sudý stupeň a nový graf $\tilde{G}$ bude eulerovský.
Tento graf obarvíme podle bodu \ref{enu:vizing-lemma-point1} a nakonec
vše, co jsme přidali, opět odebereme. Každý vrchol v $\tilde{G}$
kromě $x$ však má u sebe obě barvy hran zastoupeny v stejném počtu:
do každého vrcholu jsme přišli a zase odešli. Při odebrání hran z
$\tilde{G}$ u vrcholů se sudým stupněm už nic nezměníme, u vrcholů
s lichým stupněm (v $G$), který je alespoň $3$, pak nezmizí žádná
z barev, protože v $\tilde{G}$ u něj byla každá alespoň dvakrát.
\end{enumerate}
\end{proof}
\begin{defn}
$k$-hranové obarvení $\varphi:E\mapsto\hat{k}$ grafu $G=(V,E)$
se nazývá optimální, jestliže pro každé jiné $k$-hranové obarvení
$\tilde{\varphi}:E\mapsto\hat{k}$ platí\[
\sum_{v\in V}c_{\varphi}(v)\geq\sum_{v\in V}c_{\tilde{\varphi}}(v),\]
kde $c_{\varphi}(v)$ je počet různých barev hran vedoucích z vrcholu
$v$.
\end{defn}
\begin{rem*}
Obarvení $\varphi$ je vlastní, právě když $\left(\forall v\in V\right)\left(c_{\varphi}(v)=d_{G}(v)\right)$.
\end{rem*}
 
 
\begin{rem*}
Pojem optimální obarvení nevyužijeme nikde jinde než v důkazu Vizingovy
věty.
\end{rem*}
\begin{lem}
\label{lem:vizing-lemma-2}Nechť $\varphi$ je optimální obarvení
grafu $G=(V,E)$ a nechť existuje vrchol $u\in V$ a barvy $i,j$
takové, že barva $i$ se na vrcholu $u$ nevyskytuje vůbec a barva
$j$ se na $u$ vyskytuje alespoň dvakrát. Potom komponenta $U$ grafu\[
\tilde{G}=\left(V,\varphi^{-1}(i)\cup\varphi^{-1}(j)\right),\]
která obsahuje vrchol $u$, je kružnice liché délky.
\end{lem}
\begin{proof}
Sporem: V $\tilde{G}$ určitě platí $d_{\tilde{G}}(u)\geq2$ a počet
barev u vrcholu $u$ v grafu $\tilde{G}$ (při obarvení $\varphi$
grafu $G$) je $1$. Kdyby $U$ nebyla lichá kružnice, pak lze podle
lemmatu \ref{lem:vizing-lemma-1} najít $2$-hranové obarvení $\tilde{\varphi}$
grafu $\tilde{G}$ barvami $i,j$ takové, že $c_{\tilde{\varphi}}(u)=2$
a u ostatních vrcholů v grafu $\tilde{G}$ počet barev neklesne. Definujeme-li
pak nové obarvení $\psi$ grafu $G$ jako\[
\left(\forall e\in E\right)\left(\psi(e)=\begin{cases}
\varphi(e) & \textrm{pokud }\varphi(e)\notin\{ i,j\}\\
\tilde{\varphi}(e) & \textrm{pokud }\varphi(e)\in\{ i,j\}\end{cases}\right),\]
tak bude platit \[
\sum_{v\in V}c_{\varphi}(v)<\sum_{v\in V}c_{\psi}(v),\]
což je spor s optimalitou $\varphi$.
\end{proof}
Nyní máme již vše připraveno pro důkaz Vizingovy věty \ref{thm:Vizing}.
 
\begin{proof}
Mějme libovolný graf $G=(V,E)$. Ukážeme, že $\chi'(G)\leq\Delta+1$.
Vezmeme optimální $\left(\Delta+1\right)$-hranové obarvení $\varphi$
grafu $G$ a sporem o něm dokážeme, že je vlastní.
 
Nechť $\varphi$ není vlastní. Potom existuje $u\in V$ takový, že
$c_{\varphi}(u)<d_{G}(u)$. Proto
\begin{itemize}
\item existuje barva $i_{0}$, která na $u$ schází (taková barva existuje
na každém vrcholu) a
\item existuje barva $i_{1}$, která je na $u$ aslespoň dvakrát.
\end{itemize}
Označme $v_{1}$ vrchol, do nějž vede z $u$ hrana barvy $i_{1}$.
Dále označme $i_{2}$ barvu, která se nevyskytuje na $v_{1}$. Potom
$i_{2}$ se vyskytuje na $u$. V opačném případě totiž přebarvíme
hranu $\{ u,v_{1}\}$ na $i_{2}$, tím se počet barev na $u$ zvýší
($i_{1}$ je na $u$ dvakrát), ale počet barev na $v_{1}$ neklesne.
To je spor s optimalitou $\varphi$.
 
\hfill{}
\begin{center}
%Title: vizing1.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:20:56 1970
%%User: Pavel Strachota@DIGITHELL (DIGITHELL)
\font\thinlinefont=cmr5
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
\mbox{\beginpicture
\setcoordinatesystem units <1.00000cm,1.00000cm>
\unitlength=1.00000cm
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setshadesymbol ({\thinlinefont .})
\setlinear
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.478 19.526
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.478 20.955
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  7.620 20.003
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  7.620 20.003 10.478 19.526 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  7.620 20.003 10.478 20.955 /
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$i_{1}$}%
} [lB] at  9.049 20.839
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$i_{2}$}%
} [lB] at  9.286 20.005
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{2}$}%
} [lB] at 10.954 19.408
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{1}$}%
} [lB] at 10.954 20.836
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$u$}%
} [lB] at  7.025 19.884
\linethickness=0pt
\putrectangle corners at  6.993 21.321 and 10.986 19.209
\endpicture}
\end{center}
\hfill{}
 
Označme rekurzivně pro rostoucí $k=2,3,...$ jako $i_{k}$ barvu,
která není na $v_{k-1}$. Potom platí, že pro každé $k$ tato barva
musí být na $u$. Díky tomu lze označit vrchol, do nějž vede z $u$
hrana barvy $i_{k}$, jako $v_{k}$. Zdůvodnění uvedeného tvrzení
provedeme indukcí podle $k$: Pokud $i_{k}$ na $u$ chybí, přebarvíme
hranu $\{ u,v_{k-1}\}$ na $i_{k}$, čímž se počet barev na $v_{k-1}$
nesníží. Počet barev na $u$ se zvýší (a tak ihned dostaneme spor)
jen tehdy, pokud $i_{k-1}$ je stále na $u$, jinak pouze neklesne.
V druhém případě však získáme jiné optimální obarvení grafu $G$,
při němž $i_{k-1}$ není na $u$, což je zase spor s indukčním předpokladem.
Počáteční krok pro $k=2$ jsme již dokázali nad obrázkem.
 
Pro určité $k$ nastane situace, že barva $i_{k+1}$, která schází
na $v_{k}$, se již vyskytuje mezi barvami $i_{1},...,i_{k-1}$. Označíme
jako $l$ takový index, že $i_{k+1}=i_{l}$. To je zobrazeno na následujícím
obrázku:
 
\hfill{}
\begin{center}
%Title: vizing2.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:43:44 1970
%%User: Pavel Strachota@DIGITHELL (DIGITHELL)
\font\thinlinefont=cmr5
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
\mbox{\beginpicture
\setcoordinatesystem units <1.00000cm,1.00000cm>
\unitlength=1.00000cm
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setshadesymbol ({\thinlinefont .})
\setlinear
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  4.763 20.955
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  8.572 17.384
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  6.668 17.384
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.238 19.526
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.478 20.955
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  7.620 20.003
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  7.620 20.003  4.763 20.955 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  7.620 20.003  6.668 17.384 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  7.620 20.003  8.572 17.384 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  7.620 20.003 10.238 19.526 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  7.620 20.003 10.478 20.955 /
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$i_{l-1}$}%
} [lB] at  8.452 18.578
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{l-1}$}%
} [lB] at  9.049 17.382
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$i_{l}=i_{k+1}$}%
} [lB] at  5.478 18.576
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$i_{k}$}%
} [lB] at  6.073 20.839
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{l}$}%
} [lB] at  5.834 17.382
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{k}$}%
} [lB] at  3.929 20.836
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$i_{1}$}%
} [lB] at  8.810 20.839
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$i_{2}$}%
} [lB] at  9.286 20.005
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{2}$}%
} [lB] at 10.833 19.408
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{1}$}%
} [lB] at 10.954 20.836
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$u$}%
} [lB] at  7.501 20.481
\linethickness=0pt
\putrectangle corners at  3.897 21.321 and 10.986 17.183
\endpicture}
\end{center}
\hfill{}
 
Nyní definujeme nové obarvení $\tilde{\varphi}$, které bude pro všechny
hrany stejné jako $\varphi$, až na následující změny:\[
\left(\forall j\in\{1,...,l-1\}\right)\left(\tilde{\varphi}\left(\{ u,v_{j}\}\right)=i_{j+1}\right).\]
Potom bude při obarvení $\tilde{\varphi}$ situace následující:
 
\hfill{}
\begin{center}
%Title: vizing3.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:43:36 1970
%%User: Pavel Strachota@DIGITHELL (DIGITHELL)
\font\thinlinefont=cmr5
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
\mbox{\beginpicture
\setcoordinatesystem units <1.00000cm,1.00000cm>
\unitlength=1.00000cm
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setshadesymbol ({\thinlinefont .})
\setlinear
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  4.763 20.955
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  8.572 17.384
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  6.668 17.384
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.238 19.526
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.478 20.955
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  7.620 20.003
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  7.620 20.003  4.763 20.955 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  7.620 20.003  6.668 17.384 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  7.620 20.003  8.572 17.384 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  7.620 20.003 10.238 19.526 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  7.620 20.003 10.478 20.955 /
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$i_{l}$}%
} [lB] at  6.549 18.576
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$i_{l}$}%
} [lB] at  8.452 18.578
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$i_{3}$}%
} [lB] at  9.286 20.005
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$i_{2}$}%
} [lB] at  8.810 20.839
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{l-1}$}%
} [lB] at  9.049 17.382
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$i_{k}$}%
} [lB] at  6.073 20.839
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{l}$}%
} [lB] at  5.834 17.382
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{k}$}%
} [lB] at  3.929 20.836
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{2}$}%
} [lB] at 10.833 19.408
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{1}$}%
} [lB] at 10.954 20.836
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$u$}%
} [lB] at  7.501 20.481
\linethickness=0pt
\putrectangle corners at  3.897 21.321 and 10.986 17.183
\endpicture}
\end{center}
\hfill{}
 
\noindent Každý vrchol $v_{j}$, $j\in\{1,...,l-1\}$, dostal na hraně
$\{ u,v_{j}\}$ barvu, kterou předtím neměl. Vrchol $u$ ztratil $v_{1}$,
ale tu měl dvakrát. Nyní ji má jen jednou, ale zase má alespoň dvakrát
$i_{l}$. Z toho je jasné, že $\tilde{\varphi}$ je opět optimální
obarvení grafu $G$.
 
Definujeme ještě jedno obarvení $\tilde{\tilde{\varphi}}$, které
bude pro všechny hrany stejné jako $\varphi$, až na následující změny:\[
\left(\forall j\in\{1,...,k\}\right)\left(\tilde{\tilde{\varphi}}\left(\{ u,v_{j}\}\right)=i_{j+1}\right).\]
 Potom při obarvení $\tilde{\tilde{\varphi}}$ dostaneme situaci:
 
\hfill{}
\begin{center}
%Title: vizing4.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:51:20 1970
%%User: Pavel Strachota@DIGITHELL (DIGITHELL)
\font\thinlinefont=cmr5
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
\mbox{\beginpicture
\setcoordinatesystem units <1.00000cm,1.00000cm>
\unitlength=1.00000cm
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setshadesymbol ({\thinlinefont .})
\setlinear
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  5.000 19.526
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  4.763 20.955
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  8.572 17.384
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  6.668 17.384
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.238 19.526
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.478 20.955
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  7.620 20.003
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  7.620 20.003  5.000 19.526 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  7.620 20.003  4.763 20.955 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  7.620 20.003  6.668 17.384 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  7.620 20.003  8.572 17.384 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  7.620 20.003 10.238 19.526 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  7.620 20.003 10.478 20.955 /
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$i_{k+1}=i_{l}$}%
} [lB] at  5.596 20.959
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$i_{k}$}%
} [lB] at  5.596 20.007
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{k-1}$}%
} [lB] at  3.929 19.408
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$i_{l+1}$}%
} [lB] at  6.191 18.576
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$i_{l}$}%
} [lB] at  8.452 18.578
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$i_{3}$}%
} [lB] at  9.286 20.005
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$i_{2}$}%
} [lB] at  8.810 20.839
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{l-1}$}%
} [lB] at  9.049 17.382
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{l}$}%
} [lB] at  5.834 17.382
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{k}$}%
} [lB] at  3.929 20.836
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{2}$}%
} [lB] at 10.833 19.408
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{1}$}%
} [lB] at 10.954 20.836
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$u$}%
} [lB] at  7.501 20.481
\linethickness=0pt
\putrectangle corners at  3.897 21.442 and 10.986 17.183
\endpicture}
\end{center}
\hfill{}
 
Rovněž obarvení $\tilde{\tilde{\varphi}}$ je zřejmě optimální. Nyní
již snadno dojdeme ke sporu, když použijeme lemma \ref{lem:vizing-lemma-2}.
Komponenta podgrafu \[
\tilde{G}=\left(V,\tilde{\varphi}^{-1}(i_{0})\cup\tilde{\varphi}^{-1}(i_{l})\right),\]
obsahující vrchol $u$, má totiž být lichá kružnice. Z vrcholu $v_{l-1}$
nás tato kružnice přivede po hranách barvy $i_{0}$ a $i_{l}$ do
vrcholu $v_{l}$.
 
\hfill{}
\begin{center}
%Title: vizing5.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 19:34:00 1970
%%User: Pavel Strachota@DIGITHELL (DIGITHELL)
\font\thinlinefont=cmr5
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
\mbox{\beginpicture
\setcoordinatesystem units <1.00000cm,1.00000cm>
\unitlength=1.00000cm
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setshadesymbol ({\thinlinefont .})
\setlinear
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  7.620 20.003
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.478 20.955
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.238 19.526
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  6.668 17.384
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  8.572 17.384
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  4.763 20.955
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setdots < 0.1619cm>
{\color[rgb]{0,0,0}\plot  8.572 17.384  8.570 17.380 /
\plot  8.570 17.380  8.568 17.371 /
\plot  8.568 17.371  8.560 17.357 /
\plot  8.560 17.357  8.551 17.331 /
\plot  8.551 17.331  8.537 17.297 /
\plot  8.537 17.297  8.520 17.255 /
\plot  8.520 17.255  8.496 17.204 /
\plot  8.496 17.204  8.471 17.145 /
\plot  8.471 17.145  8.441 17.081 /
\plot  8.441 17.081  8.407 17.012 /
\plot  8.407 17.012  8.371 16.938 /
\plot  8.371 16.938  8.333 16.863 /
\plot  8.333 16.863  8.295 16.787 /
\plot  8.295 16.787  8.253 16.713 /
\plot  8.253 16.713  8.208 16.641 /
\plot  8.208 16.641  8.164 16.571 /
\plot  8.164 16.571  8.115 16.506 /
\plot  8.115 16.506  8.064 16.442 /
\plot  8.064 16.442  8.012 16.385 /
\plot  8.012 16.385  7.954 16.332 /
\plot  7.954 16.332  7.895 16.286 /
\plot  7.895 16.286  7.832 16.248 /
\plot  7.832 16.248  7.764 16.218 /
\plot  7.764 16.218  7.692 16.199 /
\plot  7.692 16.199  7.620 16.192 /
\plot  7.620 16.192  7.548 16.199 /
\plot  7.548 16.199  7.476 16.218 /
\plot  7.476 16.218  7.408 16.248 /
\plot  7.408 16.248  7.345 16.286 /
\plot  7.345 16.286  7.286 16.332 /
\plot  7.286 16.332  7.228 16.385 /
\plot  7.228 16.385  7.176 16.442 /
\plot  7.176 16.442  7.125 16.506 /
\plot  7.125 16.506  7.076 16.571 /
\plot  7.076 16.571  7.032 16.641 /
\plot  7.032 16.641  6.987 16.713 /
\plot  6.987 16.713  6.945 16.787 /
\plot  6.945 16.787  6.905 16.863 /
\plot  6.905 16.863  6.869 16.938 /
\plot  6.869 16.938  6.833 17.012 /
\plot  6.833 17.012  6.799 17.081 /
\plot  6.799 17.081  6.769 17.145 /
\plot  6.769 17.145  6.744 17.204 /
\plot  6.744 17.204  6.720 17.255 /
\plot  6.720 17.255  6.703 17.297 /
\plot  6.703 17.297  6.689 17.331 /
\plot  6.689 17.331  6.680 17.357 /
\plot  6.680 17.357  6.672 17.371 /
\plot  6.672 17.371  6.670 17.380 /
\plot  6.670 17.380  6.668 17.384 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setsolid
{\color[rgb]{0,0,0}\plot  7.620 20.003 10.478 20.955 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  7.620 20.003 10.238 19.526 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  7.620 20.003  8.572 17.384 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  7.620 20.003  6.668 17.384 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  7.620 20.003  4.763 20.955 /
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$u$}%
} [lB] at  7.501 20.481
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{1}$}%
} [lB] at 10.954 20.836
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{2}$}%
} [lB] at 10.833 19.408
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{k}$}%
} [lB] at  3.929 20.836
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{l}$}%
} [lB] at  5.834 17.382
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$i_{k}$}%
} [lB] at  6.073 20.839
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{l-1}$}%
} [lB] at  9.049 17.382
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$i_{2}$}%
} [lB] at  8.810 20.839
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$i_{3}$}%
} [lB] at  9.286 20.005
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$i_{l}$}%
} [lB] at  8.452 18.578
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$i_{l}$}%
} [lB] at  6.549 18.576
\linethickness=0pt
\putrectangle corners at  3.897 21.321 and 10.986 16.146
\endpicture}
\end{center}
\hfill{}
 
\noindent Zároveň však platí, že i komponenta podgrafu\[
\tilde{\tilde{G}}=\left(V,\tilde{\tilde{\varphi}}^{-1}(i_{0})\cup\tilde{\tilde{\varphi}}^{-1}(i_{l})\right),\]
obsahující vrchol $u$, je lichá kružnice. Z vrcholu $v_{l-1}$ nás
tato kružnice přivede po hranách barvy $i_{0}$ a $i_{l}$ do vrcholu
$v_{k}$.
 
\noindent \hfill{}
\begin{center}
 
%Title: vizing6.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 20:44:00 1970
%%User: Pavel Strachota@DIGITHELL (DIGITHELL)
\font\thinlinefont=cmr5
%
\begingroup\makeatletter\ifx\SetFigFont\undefined%
\gdef\SetFigFont#1#2#3#4#5{%
  \reset@font\fontsize{#1}{#2pt}%
  \fontfamily{#3}\fontseries{#4}\fontshape{#5}%
  \selectfont}%
\fi\endgroup%
\mbox{\beginpicture
\setcoordinatesystem units <1.00000cm,1.00000cm>
\unitlength=1.00000cm
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setshadesymbol ({\thinlinefont .})
\setlinear
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  5.000 19.526
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  4.763 20.955
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  8.572 17.384
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  6.668 17.384
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.238 19.526
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.478 20.955
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at  7.620 20.003
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setdots < 0.1619cm>
{\color[rgb]{0,0,0}\plot  8.572 17.384  8.570 17.382 /
\plot  8.570 17.382  8.566 17.378 /
\plot  8.566 17.378  8.558 17.371 /
\plot  8.558 17.371  8.545 17.361 /
\plot  8.545 17.361  8.526 17.344 /
\plot  8.526 17.344  8.503 17.323 /
\plot  8.503 17.323  8.471 17.295 /
\plot  8.471 17.295  8.433 17.264 /
\plot  8.433 17.264  8.386 17.225 /
\plot  8.386 17.225  8.335 17.181 /
\plot  8.335 17.181  8.276 17.134 /
\plot  8.276 17.134  8.213 17.081 /
\plot  8.213 17.081  8.141 17.024 /
\plot  8.141 17.024  8.064 16.965 /
\plot  8.064 16.965  7.984 16.904 /
\plot  7.984 16.904  7.899 16.840 /
\plot  7.899 16.840  7.813 16.775 /
\plot  7.813 16.775  7.719 16.711 /
\plot  7.719 16.711  7.626 16.645 /
\plot  7.626 16.645  7.529 16.582 /
\plot  7.529 16.582  7.430 16.521 /
\plot  7.430 16.521  7.328 16.459 /
\plot  7.328 16.459  7.226 16.402 /
\plot  7.226 16.402  7.120 16.347 /
\plot  7.120 16.347  7.013 16.294 /
\plot  7.013 16.294  6.902 16.245 /
\plot  6.902 16.245  6.788 16.201 /
\plot  6.788 16.201  6.672 16.161 /
\plot  6.672 16.161  6.553 16.125 /
\plot  6.553 16.125  6.430 16.093 /
\plot  6.430 16.093  6.303 16.068 /
\plot  6.303 16.068  6.172 16.049 /
\plot  6.172 16.049  6.037 16.038 /
\plot  6.037 16.038  5.899 16.034 /
\plot  5.899 16.034  5.759 16.038 /
\plot  5.759 16.038  5.618 16.051 /
\plot  5.618 16.051  5.476 16.074 /
\plot  5.476 16.074  5.342 16.106 /
\plot  5.342 16.106  5.215 16.144 /
\plot  5.215 16.144  5.091 16.186 /
\plot  5.091 16.186  4.974 16.235 /
\plot  4.974 16.235  4.864 16.286 /
\plot  4.864 16.286  4.760 16.336 /
\plot  4.760 16.336  4.665 16.387 /
\plot  4.665 16.387  4.578 16.440 /
\plot  4.578 16.440  4.498 16.489 /
\plot  4.498 16.489  4.424 16.538 /
\plot  4.424 16.538  4.358 16.586 /
\plot  4.358 16.586  4.297 16.631 /
\plot  4.297 16.631  4.242 16.675 /
\plot  4.242 16.675  4.191 16.715 /
\plot  4.191 16.715  4.144 16.758 /
\plot  4.144 16.758  4.102 16.796 /
\plot  4.102 16.796  4.064 16.834 /
\plot  4.064 16.834  4.026 16.872 /
\plot  4.026 16.872  3.992 16.910 /
\plot  3.992 16.910  3.958 16.948 /
\plot  3.958 16.948  3.924 16.986 /
\plot  3.924 16.986  3.893 17.024 /
\plot  3.893 17.024  3.859 17.067 /
\plot  3.859 17.067  3.827 17.111 /
\plot  3.827 17.111  3.793 17.156 /
\plot  3.793 17.156  3.757 17.206 /
\plot  3.757 17.206  3.721 17.259 /
\plot  3.721 17.259  3.683 17.319 /
\plot  3.683 17.319  3.645 17.380 /
\plot  3.645 17.380  3.603 17.448 /
\plot  3.603 17.448  3.560 17.522 /
\plot  3.560 17.522  3.516 17.602 /
\plot  3.516 17.602  3.471 17.689 /
\plot  3.471 17.689  3.427 17.782 /
\plot  3.427 17.782  3.382 17.882 /
\plot  3.382 17.882  3.340 17.987 /
\plot  3.340 17.987  3.300 18.098 /
\plot  3.300 18.098  3.266 18.214 /
\plot  3.266 18.214  3.236 18.335 /
\plot  3.236 18.335  3.213 18.455 /
\plot  3.213 18.455  3.200 18.584 /
\plot  3.200 18.584  3.196 18.709 /
\plot  3.196 18.709  3.200 18.834 /
\plot  3.200 18.834  3.215 18.955 /
\plot  3.215 18.955  3.236 19.071 /
\plot  3.236 19.071  3.266 19.181 /
\plot  3.266 19.181  3.300 19.289 /
\plot  3.300 19.289  3.340 19.393 /
\plot  3.340 19.393  3.385 19.490 /
\plot  3.385 19.490  3.433 19.586 /
\plot  3.433 19.586  3.488 19.679 /
\plot  3.488 19.679  3.545 19.768 /
\plot  3.545 19.768  3.605 19.852 /
\plot  3.605 19.852  3.670 19.937 /
\plot  3.670 19.937  3.736 20.017 /
\plot  3.736 20.017  3.804 20.096 /
\plot  3.804 20.096  3.873 20.172 /
\plot  3.873 20.172  3.945 20.246 /
\plot  3.945 20.246  4.017 20.320 /
\plot  4.017 20.320  4.089 20.388 /
\plot  4.089 20.388  4.161 20.455 /
\plot  4.161 20.455  4.233 20.519 /
\plot  4.233 20.519  4.301 20.580 /
\plot  4.301 20.580  4.367 20.635 /
\plot  4.367 20.635  4.428 20.688 /
\plot  4.428 20.688  4.487 20.737 /
\plot  4.487 20.737  4.540 20.779 /
\plot  4.540 20.779  4.587 20.820 /
\plot  4.587 20.820  4.629 20.851 /
\plot  4.629 20.851  4.665 20.881 /
\plot  4.665 20.881  4.695 20.904 /
\plot  4.695 20.904  4.718 20.921 /
\plot  4.718 20.921  4.735 20.936 /
\plot  4.735 20.936  4.748 20.944 /
\plot  4.748 20.944  4.756 20.951 /
\plot  4.756 20.951  4.760 20.953 /
\plot  4.760 20.953  4.763 20.955 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setsolid
{\color[rgb]{0,0,0}\plot  7.620 20.003  5.000 19.526 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  7.620 20.003  4.763 20.955 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  7.620 20.003  6.668 17.384 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  7.620 20.003  8.572 17.384 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  7.620 20.003 10.238 19.526 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  7.620 20.003 10.478 20.955 /
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$i_{k+1}=i_{l}$}%
} [lB] at  5.596 20.959
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$i_{k}$}%
} [lB] at  5.596 20.007
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{k-1}$}%
} [lB] at  3.929 19.408
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$i_{l+1}$}%
} [lB] at  6.191 18.576
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$i_{l}$}%
} [lB] at  8.452 18.578
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$i_{3}$}%
} [lB] at  9.286 20.005
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$i_{2}$}%
} [lB] at  8.810 20.839
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{l-1}$}%
} [lB] at  9.049 17.382
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{l}$}%
} [lB] at  5.834 17.382
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{k}$}%
} [lB] at  3.571 20.836
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{2}$}%
} [lB] at 10.833 19.408
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v_{1}$}%
} [lB] at 10.954 20.836
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$u$}%
} [lB] at  7.501 20.481
\linethickness=0pt
\putrectangle corners at  3.150 21.442 and 10.986 15.987
\endpicture}
\end{center}
\hfill{}
 
\noindent To je ale spor, protože jediné hrany, které mají v obarvení
$\tilde{\tilde{\varphi}}$ barvu odlišnou od barvy v obarvení $\tilde{\varphi}$,
jsou hrany $\{ u,v_{l}\},\{ u,v_{l+1}\},...,\{ u,v_{k}\}$, takže
kružnice vedoucí přes $v_{l-1}$ se nemůže tímto způsobem změnit jen
díky změně obarvení z $\tilde{\varphi}$ na $\tilde{\tilde{\varphi}}$.
\end{proof}