Součásti dokumentu 01ZTGA
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}
