01ZTGA:Kapitola1 11: Porovnání verzí
Z WikiSkripta FJFI ČVUT v Praze
(Založena nová stránka: %\wikiskriptum{01ZTGA}) |
|||
Řádka 1: | Řádka 1: | ||
%\wikiskriptum{01ZTGA} | %\wikiskriptum{01ZTGA} | ||
+ | |||
+ | \section{Vrcholové obarvení grafu} | ||
+ | |||
+ | \begin{defn} | ||
+ | Nechť $G=(V,E)$ je graf, $k\in\N$. $k$-\textbf{vrcholovým obarvením} | ||
+ | (angl. $k$\emph{-vertex colouring}) grafu $G$ nazveme zobrazení | ||
+ | $\varphi:V\mapsto\hat{k}$. $\varphi$ se nazývá \textbf{vlastní} | ||
+ | (angl. \emph{proper}) $k$-vrcholové obarvení grafu $G$, jestliže | ||
+ | platí\[ | ||
+ | \left(\forall u,v\in V\right)\left(\varphi(u)=\varphi(v)\Rightarrow\{ u,v\}\notin E\right),\] | ||
+ | tj. jestliže stejně barevné vrcholy nejsou spojeny hranou. Minimální | ||
+ | $k$ takové, že existuje $k$-vrcholové vlastní obarvení grafu $G$, | ||
+ | se nazývá \textbf{barevnost} (angl. \emph{chromatic number}) grafu | ||
+ | $G$ a značí se $\chi(G)$. | ||
+ | \end{defn} | ||
+ | \begin{example*} | ||
+ | Jestliže vrcholy reprezentují účastníky reality show a hrany vedou | ||
+ | mezi těmi, kteří se nesnášejí, pak $\chi(G)$ je minimální počet skupin, | ||
+ | do nichž lze soutěžící rozdělit tak, aby v žádné skupině nebyli dva, | ||
+ | kteří se nesnášejí. | ||
+ | \end{example*} | ||
+ | \begin{rem*} | ||
+ | ~ | ||
+ | \begin{itemize} | ||
+ | \item $\chi(G)=1$ $\Leftrightarrow$ $G=(V,\emptyset)$. | ||
+ | \item $\chi(G)=2$ $\Leftrightarrow$ $G$ je bipartitní s alespoň jednou | ||
+ | hranou ($\Leftrightarrow$ v $G$ není kružnice liché délky). | ||
+ | \item $\chi(G)=p,p\geq3$ $\Leftrightarrow$ ?? | ||
+ | \end{itemize} | ||
+ | Rozhodnout o tom, zda $\chi(G)=p$, je pro obecný graf NP-úplná úloha. | ||
+ | Podle předchozích bodů můžeme jen ověřit, jestli $\chi(G)\geq3$ nebo | ||
+ | ne. | ||
+ | \end{rem*} | ||
+ | \begin{rem} | ||
+ | Zřejmě vždy platí $\chi(G)\leq n=\# V$. Jestliže obarvíme každý vrchol | ||
+ | jinou barvou, dostaneme vlastní obarvení. Přitom když $G=K_{n}$, | ||
+ | tj. je-li $G$ úplným grafem na $n$ vrcholech, tak $\chi(G)=n$. | ||
+ | Platí i opačná implikace, protože chybí-li mezi dvěma vrcholy hrana, | ||
+ | lze je obarvit stejnou barvou a zbylé vrcholy opět obarvit různě. | ||
+ | Celkem tedy\[ | ||
+ | \chi(G)=n\Leftrightarrow G=K_{n}.\] | ||
+ | |||
+ | \end{rem} | ||
+ | \begin{defn} | ||
+ | \label{def:klika-nez-mnozina}Nechť $G=(V,E)$ je graf, $k\in\N$. | ||
+ | \begin{itemize} | ||
+ | \item \textbf{Klikou} (angl. \emph{clique}) velikosti $k$ v $G$ rozumíme | ||
+ | množinu vrcholů $S\subset V$ takovou, že podgraf $G[S]=\left(S,E\cap\binom{S}{2}\right)$ | ||
+ | indukovaný množinou $S$ je úplný, tj. každé dva vrcholy z $S$ jsou | ||
+ | spojeny hranou v $G$. | ||
+ | \item $S\subset V$ se nazývá \textbf{nezávislá množina} (angl. \emph{independent | ||
+ | set}) velikosti $k$ v $G$, jestliže $E\cap\binom{S}{2}=\emptyset$, | ||
+ | tj. jestliže žádné dva vrcholy z $S$ nejsou spojeny hranou v grafu | ||
+ | $G$. | ||
+ | \item $S\subset V$ se nazývá \textbf{vrcholové pokrytí} (angl. \emph{covering}) | ||
+ | grafu $G$, jestliže $\left(\forall e\in E\right)\left(\exists v\in S\right)\left(v\in e\right)$, | ||
+ | tj. jestliže každá hrana v $G$ má alespoň jeden konec v $S$. | ||
+ | \end{itemize} | ||
+ | Maximální velikost kliky v grafu $G$ značíme $\omega(G)$, maximální | ||
+ | velikost nezávislé množiny značíme $\alpha(G)$. | ||
+ | \end{defn} | ||
+ | \begin{rem*} | ||
+ | V přednášce někdy klikou velikosti $k$ nazýváme též úplný podgraf | ||
+ | $K_{k}=G[S]$, který množina $S$ indukuje. | ||
+ | \end{rem*} | ||
+ | \begin{rem} | ||
+ | \label{rem:alfa-omega-v-doplnku-G}Je-li $S$ nezávislá množina v | ||
+ | $G$, pak $S$ je klika v $\bar{G}$ a naopak. Proto zřejmě platí\begin{eqnarray*} | ||
+ | \alpha(\bar{G}) & = & \omega(G)\\ | ||
+ | \omega(\bar{G)} & = & \alpha(G).\end{eqnarray*} | ||
+ | |||
+ | \end{rem} | ||
+ | \begin{rem*} | ||
+ | Klikami a nezávislými množinami se budeme v různých souvislostech | ||
+ | zabývat především v druhé části přednášky. Nyní tuto definici budeme | ||
+ | potřebovat jen na několika málo místech. | ||
+ | \end{rem*} | ||
+ | |||
+ | |||
+ | \begin{rem*} | ||
+ | Nechť $\varphi$ je vlastní $\chi(G)$-vrcholové obarvení grafu $G=(V,E)$, | ||
+ | $i\in\widehat{\chi(G)}$. Potom mezi vrcholy z $\varphi^{-1}(i)$ | ||
+ | nevede hrana, neboli $\varphi^{-1}(i)$ je nezávislá množina. Tím | ||
+ | pádem\[ | ||
+ | \#\varphi^{-1}(i)\leq\alpha(G)\] | ||
+ | a přitom platí\[ | ||
+ | \bigcup_{i=1}^{\chi(G)}\#\varphi^{-1}(i)=V.\] | ||
+ | |||
+ | \end{rem*} | ||
+ | \begin{thm} | ||
+ | Nechť $G=(V,E)$ je graf. Potom platí\begin{eqnarray*} | ||
+ | \# V & \leq & \alpha(G)\cdot\chi(G)\\ | ||
+ | \omega(G) & \leq & \chi(G).\end{eqnarray*} | ||
+ | |||
+ | \end{thm} | ||
+ | \begin{proof} | ||
+ | První tvrzení plyne okamžitě z předchozí poznámky. Druhé tvrzení je | ||
+ | zřejmé: V $G$ existuje klika velikosti $\omega(G)$, jejíž vrcholy | ||
+ | musí mít při vlastním obarvení grafu $G$ $\omega(G)$ různých barev. | ||
+ | \end{proof} | ||
+ | \begin{rem*} | ||
+ | ~ | ||
+ | \begin{enumerate} | ||
+ | \item Jestliže $H\subset G$, potom $\chi(H)\leq\chi(G)$. | ||
+ | \item Platí-li $G=G_{1}\cup G_{2}\cup...\cup G_{r}$, kde $G_{i}$ jsou | ||
+ | komponenty grafu $G$, potom zřejmě\[ | ||
+ | \chi(G)=\max_{i\in\hat{r}}\chi(G_{i}).\] | ||
+ | |||
+ | \end{enumerate} | ||
+ | \end{rem*} | ||
+ | \begin{thm} | ||
+ | Nechť $G=(V,E)$ je graf. Potom $\chi(G)\leq\Delta(G)+1$. | ||
+ | \end{thm} | ||
+ | \begin{proof} | ||
+ | Tvrzení je formálně shodné s Vizingovou větou \ref{thm:Vizing} pro | ||
+ | hranovou barevnost. Zde je však důkaz snadný. ,,Poctivě{}`` jej | ||
+ | lze provést indukcí podle $n=\# V$. | ||
+ | |||
+ | Pro $n=1$ je to jasné: $\Delta(G)=0$, $\chi(G)=1=\Delta(G)+1$. | ||
+ | |||
+ | Indukční krok $n-1\to n$: V $G$ najdeme vrchol $u\in V$ takový, | ||
+ | že $d_{G}(u)=\Delta(G)$. Samozřejmě je $\Delta(G\backslash u)\leq\Delta(G)$. | ||
+ | Z indukčního předpokladu je $\chi(G\backslash u)\leq\Delta(G\backslash u)+1\leq\Delta(G)+1$. | ||
+ | Najdeme tedy vlastní obarvení grafu $G\backslash u$ pomocí $\Delta(G)+1$ | ||
+ | barev. Pokud nyní přidáme zpět vrchol $u$, který má $\Delta(G)$ | ||
+ | sousedů, bude možné jej rovněž obarvit jednou z $\Delta(G)+1$ barev. | ||
+ | Celý $G$ je tak obarven pomocí $\Delta(G)+1$ barev. | ||
+ | \end{proof} | ||
+ | \begin{rem*} | ||
+ | Myšlenku předchozího důkazu lze shrnout jednoduše: Postupně barvíme | ||
+ | jeden vrchol za druhým první dostupnou barvou. Nikdy se nemůže stát, | ||
+ | že bychom neměli k dispozici žádnou volnou barvu, protože každý vrchol | ||
+ | má méně sousedů, než kolik máme barev. | ||
+ | \end{rem*} | ||
+ | |||
+ | |||
+ | \begin{rem*} | ||
+ | Dolní odhad na $\chi(G)$ není možné pomocí $\Delta(G)$ nijak vyjádřit: | ||
+ | \begin{itemize} | ||
+ | \item Úplný graf $K_{n}$ na $n$ vrcholech má $\chi(K_{n})=n=\Delta(G)+1$. | ||
+ | \item Úplný bipartitní graf na $1+(n-1)$ vrcholech, tj. graf $S_{n-1}$ | ||
+ | (viz definice \ref{def:specialni-grafy}) má $\Delta(S_{n-1})=n-1$, | ||
+ | ale $\chi(G)=2$. | ||
+ | \end{itemize} | ||
+ | \end{rem*} | ||
+ | \begin{thm} | ||
+ | \label{thm:barevnost-s-doplnkem}Pro každý graf $G=(V,E)$ platí: | ||
+ | \begin{enumerate} | ||
+ | \item $\chi(G)+\chi(\bar{G})\leq n+1$, | ||
+ | \item $\chi(G)\cdot\chi(\bar{G})\geq n$. | ||
+ | \end{enumerate} | ||
+ | \end{thm} | ||
+ | Připravíme si dvě pomocná tvrzení, z nichž již plynou jednotlivé nerovnosti. | ||
+ | |||
+ | \begin{lem} | ||
+ | Buďte $G_{1}=(V_{1},E_{1}),G_{2}=(V_{2},E_{2})$ dva grafy. Potom | ||
+ | platí\[ | ||
+ | \chi(G_{1}\cup G_{2})\leq\chi(G_{1})\cdot\chi(G_{2}).\] | ||
+ | |||
+ | \end{lem} | ||
+ | \begin{proof} | ||
+ | Zřejmě platí $\chi(G_{1})=\chi(\tilde{G}_{1})$, kde $\tilde{G}_{1}=(V_{1}\cup V_{2},E_{1})$, | ||
+ | a stejně $\chi(G_{2})=\chi(\tilde{G}_{2})$, kde $\tilde{G}_{2}=(V_{1}\cup V_{2},E_{2})$. | ||
+ | BÚNO je proto možné předpokládat $V_{1}=V_{2}(:=V)$. | ||
+ | |||
+ | Z předpokladu existují obarvení grafů $G_{1}$ a $G_{2}$\begin{eqnarray*} | ||
+ | \varphi_{1} & : & V\mapsto\left\{ 1,2,...,\chi(G_{1})\right\} ,\\ | ||
+ | \varphi_{2} & : & V\mapsto\left\{ 1,2,...,\chi(G_{2})\right\} .\end{eqnarray*} | ||
+ | Najdeme obarvení grafu $G_{1}\cup G_{2}$ pomocí $\chi(G_{1})\cdot\chi(G_{2})$ | ||
+ | barev. Definujme nyní pro každé $v\in V$\[ | ||
+ | \psi(v)=\left(\varphi_{1}(v),\varphi_{2}(v)\right).\] | ||
+ | Potom pro každé $u,v\in V$ platí $\left(\psi(u)=\psi(v)\right)$$\Rightarrow$$\left(\varphi_{1}(u)=\varphi_{1}(v)\wedge\varphi_{2}(u)=\varphi_{2}(v)\right)$$\Rightarrow$\\ | ||
+ | $\Rightarrow$$\left(\{ u,v\}\notin E_{1}\wedge\{ u,v\}\notin E_{2}\right)$$\Rightarrow$$\{ u,v\}\notin E_{1}\cup E_{2}$. | ||
+ | Zobrazení $\psi$ je\[ | ||
+ | \psi:V\mapsto\left\{ 1,2,...,\chi(G_{1})\right\} \times\left\{ 1,2,...,\chi(G_{2})\right\} .\] | ||
+ | Obor hodnot zobrazení $\psi$ je však (množinově) izomorfní s množinou | ||
+ | $\left\{ 1,2,...,\chi(G_{1})\cdot\chi(G_{2})\right\} $. Abychom korektně | ||
+ | definovali vrcholové obarvení grafu $G_{1}\cup G_{2}$, označme \[ | ||
+ | B:\left\{ 1,2,...,\chi(G_{1})\right\} \times\left\{ 1,2,...,\chi(G_{2})\right\} \mapsto\left\{ 1,2,...,\chi(G_{1})\cdot\chi(G_{2})\right\} \] | ||
+ | bijekci mezi uvedenými množinami. Potom lze pro každé $v\in V$ definovat | ||
+ | $\chi(G_{1})\cdot\chi(G_{2})$-vrcholové obarvení grafu $G_{1}\cup G_{2}$ | ||
+ | takto:\[ | ||
+ | \varphi(v)=B(\psi(v)).\] | ||
+ | |||
+ | |||
+ | Pro $\varphi$ platí $\left(\forall u,v\in V\right)\left(\varphi(u)=\varphi(v)\Rightarrow\{ u,v\}\notin E_{1}\cup E_{2}\right)$, | ||
+ | takže se skutečně jedná o vrcholové obarvení. | ||
+ | \end{proof} | ||
+ | \begin{cor*} | ||
+ | Platí tvrzení $(2)$ věty \ref{thm:barevnost-s-doplnkem}. | ||
+ | \end{cor*} | ||
+ | \begin{proof} | ||
+ | Protože $G\cup\bar{G}=K_{n}$, tak\[ | ||
+ | n=\chi(K_{n})=\chi(G\cup\bar{G})\leq\chi(G)\cdot\chi(\bar{G}).\] | ||
+ | |||
+ | \end{proof} | ||
+ | \begin{lem} | ||
+ | Buď $G=(V,E)$ graf. Nechť existuje disjunktní rozklad množiny vrcholů | ||
+ | $V=V_{1}\cup V_{2}\cup...\cup V_{k}$ takový, že\[ | ||
+ | \left(\forall i,j\in\hat{k},i\neq j\right)\left(\exists u\in V_{i}\right)\left(\exists v\in V_{j}\right)\left(\{ u,v\}\notin E\right).\] | ||
+ | Potom $\chi(G)\leq n+1-k$. | ||
+ | \end{lem} | ||
+ | \begin{proof} | ||
+ | Indukcí podle $k$. Pro $k=1$ máme $\chi(G)\leq n+1-1=n$, což je | ||
+ | pravda. | ||
+ | |||
+ | Indukční krok $k-1\to k$: Platí $\chi(G\backslash V_{k})=\left(n-\# V_{k}\right)+1-(k-1)=\left(n-\# V_{k}\right)+2-k$. | ||
+ | Nyní vezmeme $\# V_{k}$ nových barev a obarvíme vrcholy z $V_{k}$ | ||
+ | těmito barvami, každý vrchol jinou barvou. Máme tak obarvený celý | ||
+ | graf, a to $\leq\left(n-\# V_{k}\right)+2-k+\# V_{k}=n+2-k$ barvami. | ||
+ | Pokud je tento počet barev $\leq n+1-k$, je hotovo. Jestliže je použito | ||
+ | právě $n+2-k$ barev, musíme pokračovat a obarvení upravit. Z předpokladu | ||
+ | platí\[ | ||
+ | \left(\forall i\in\{1,2,...,k-1\}\right)\left(\exists x_{i}\in V_{i}\right)\left(\exists y_{i}\in V_{k}\right)\left(\{ x_{i},y_{i}\}\notin E\right).\] | ||
+ | Množina $V\backslash\{ x_{1},x_{2},...,x_{k-1}\}$ má počet vrcholů | ||
+ | $n-(k-1)=n+1-k$, což je méně, než počet použitých barev. Proto existuje | ||
+ | barva $b$, která se vyskytuje pouze na vrcholech $x_{1},x_{2},...,x_{k-1}$. | ||
+ | Této barvy se zbavíme tak, že každý vrchol $x_{i}$ ($i\in\{1,...,k-1\}$), | ||
+ | který má barvu $b$, přebarvíme na barvu vrcholu $y_{i}$. Potom nové | ||
+ | obarvení je stále vlastní. $\{ x_{i},y_{i}\}$ totiž nejsou v hraně, | ||
+ | a i kdyby různým $x_{i},x_{j}$ příslušel stejný vrchol $y_{i}=y_{j}$, | ||
+ | potom, protože oba vrcholy $x_{i},x_{j}$ měly stejnou barvu $b$, | ||
+ | lze je opět obarvit stejnou barvou - barvou vrcholu $y_{i}$. | ||
+ | \end{proof} | ||
+ | \begin{cor*} | ||
+ | Platí tvrzení $(1)$ věty \ref{thm:barevnost-s-doplnkem}. | ||
+ | \end{cor*} | ||
+ | \begin{proof} | ||
+ | Označme $k=\chi(G)$. Nechť $\varphi$ je vlastní $k$-vrcholové obarvení | ||
+ | $G$. Pro každé $i\in\hat{k}$ označme\[ | ||
+ | V_{i}:=\varphi^{-1}(i).\] | ||
+ | Potom platí, že \begin{equation} | ||
+ | \left(\forall i,j\in\hat{k},1\leq i\leq j\leq k\right)\left(\exists u\in V_{i}\right)\left(\exists v\in V_{j}\right)\left(\{ u,v\}\in E\right).\label{eq:hranaViVj}\end{equation} | ||
+ | Kdyby tomu tak nebylo, tj. kdyby\[ | ||
+ | \left(\exists i,j\in\hat{k},1\leq i\leq j\leq k\right)\left(\forall u\in V_{i}\right)\left(\forall v\in V_{j}\right)\left(\{ u,v\}\notin E\right),\] | ||
+ | bylo by možné vrcholy z $V_{i}$ i z $V_{j}$ obarvit stejnou barvou, | ||
+ | a tak by $\chi(G)<k$, což je spor. Vezměme nyní graf $\bar{G}$ a | ||
+ | definujme na něm stejný rozklad $V=\bigcup_{i=1}^{k}V_{i}$. Potom | ||
+ | z (\ref{eq:hranaViVj}) vznikne pro graf $\bar{G}$ přímo předpoklad | ||
+ | lemmatu. Proto\[ | ||
+ | \chi(\bar{G})\leq n+1-k=n+1-\chi(G),\] | ||
+ | což už je první tvrzení věty \ref{thm:barevnost-s-doplnkem}. | ||
+ | \end{proof} | ||
+ | |||
+ | \subsection{$k$-kritické grafy} | ||
+ | |||
+ | \begin{defn} | ||
+ | Řekneme, že graf $G=(V,E)$ je $k$-\textbf{kritický}, jestliže $\chi(G)=k$ | ||
+ | a pro každý vlastní podgraf $H\subsetneqq G$ je $\chi(H)<\chi(G)$. | ||
+ | \end{defn} | ||
+ | \begin{obs} | ||
+ | $k$-kritický graf je souvislý. | ||
+ | \end{obs} | ||
+ | \begin{proof} | ||
+ | Víme, že má-li $G$ komponenty $G_{1},...,G_{r}$, tak potom\[ | ||
+ | \chi(G)=\max_{i\in\hat{r}}\chi(G_{i}).\] | ||
+ | Je-li $r\geq2$, existuje jedna nebo více komponent, které lze z grafu | ||
+ | $G$ odebrat, aniž se sníží jeho barevnost. Proto takový $G$ není | ||
+ | $k$-kritický. | ||
+ | \end{proof} | ||
+ | \begin{rem} | ||
+ | \label{rem:123kriticke-grafy}~ | ||
+ | \begin{itemize} | ||
+ | \item $1$-kritický graf je $G=\{\{ v\},\emptyset\}$. | ||
+ | \item $2$-kritický graf je $G=\{\{ u,v\},\{\{ u,v\}\}\}$. | ||
+ | \item $3$-kritický graf je $C_{2n-1}$ (kružnice liché délky). | ||
+ | \end{itemize} | ||
+ | \end{rem} | ||
+ | \begin{proof} | ||
+ | První dvě tvrzení jsou zřejmá. Dále víme, že $\chi(G)=2$, právě když | ||
+ | $G$ je bipartitní graf. $3$-kritický graf tedy nesmí být bipartitní, | ||
+ | ale odebráním čehokoliv z něj musí bipartitní graf vzniknout. Jediný | ||
+ | graf, který to splňuje, je kružnice liché délky bez dalších odboček. | ||
+ | \end{proof} | ||
+ | \begin{rem*} | ||
+ | $4$-kritický graf vidíme na obrázku \ref{cap:4kriticky-graf}. Odebereme-li | ||
+ | totiž hranu z obvodu, lze vrcholy po obvodě obarvit jen barvami $1$ | ||
+ | a $2$ a vrchol uprostřed barvou $3$. Odebereme-li hranu vedoucí | ||
+ | do středu, obarvíme vrcholy po obvodu kromě vrcholu $v_{0}$, ze kterého | ||
+ | jsme odebrali hranu, barvami $1$ a $2$. Vrchol $v_{0}$ a střed | ||
+ | pak obarvíme barvou $3$.% | ||
+ | \begin{figure} | ||
+ | \begin{center} | ||
+ | %Title: 4kriticky.fig | ||
+ | %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 | ||
+ | %%CreationDate: Thu Feb 12 19:45:28 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 8.333 18.098 | ||
+ | }% | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 8.096 19.050 | ||
+ | }% | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 8.333 20.003 | ||
+ | }% | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.954 19.765 | ||
+ | }% | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.954 18.337 | ||
+ | }% | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.525 17.621 | ||
+ | }% | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.525 20.479 | ||
+ | }% | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.525 19.050 | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness=1pt | ||
+ | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
+ | {\color[rgb]{0,0,0}\putrule from 8.096 19.050 to 9.525 19.050 | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness=1pt | ||
+ | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
+ | {\color[rgb]{0,0,0}\putrule from 9.525 17.621 to 9.525 19.050 | ||
+ | \plot 9.525 19.050 8.333 18.098 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness=1pt | ||
+ | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
+ | {\color[rgb]{0,0,0}\plot 10.954 19.765 9.525 19.050 / | ||
+ | \plot 9.525 19.050 10.954 18.337 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness=1pt | ||
+ | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
+ | {\color[rgb]{0,0,0}\plot 8.333 20.003 9.525 19.050 / | ||
+ | \putrule from 9.525 19.050 to 9.525 20.479 | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness=1pt | ||
+ | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
+ | {\color[rgb]{0,0,0}\plot 8.333 20.003 9.525 20.479 / | ||
+ | \plot 9.525 20.479 10.954 19.765 / | ||
+ | \putrule from 10.954 19.765 to 10.954 18.337 | ||
+ | \plot 10.954 18.337 9.525 17.621 / | ||
+ | \plot 9.525 17.621 8.333 18.098 / | ||
+ | \plot 8.333 18.098 8.096 19.050 / | ||
+ | \plot 8.096 19.050 8.333 20.003 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}4}% | ||
+ | } [lB] at 9.644 19.408 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}3}% | ||
+ | } [lB] at 7.739 19.884 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}2}% | ||
+ | } [lB] at 7.499 18.931 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}1}% | ||
+ | } [lB] at 7.739 17.979 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}2}% | ||
+ | } [lB] at 9.406 16.787 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}1}% | ||
+ | } [lB] at 11.311 18.216 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}2}% | ||
+ | } [lB] at 11.309 19.647 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}1}% | ||
+ | } [lB] at 9.406 20.955 | ||
+ | \linethickness=0pt | ||
+ | \putrectangle corners at 7.468 21.552 and 11.343 16.756 | ||
+ | \endpicture} | ||
+ | \end{center} | ||
+ | |||
+ | |||
+ | \caption{\label{cap:4kriticky-graf}$4$-kritický graf} | ||
+ | \end{figure} | ||
+ | |||
+ | \end{rem*} | ||
+ | \begin{rem} | ||
+ | Každý graf $G$ s barevností $k=\chi(G)$ obsahuje $k$-kritický podgraf. | ||
+ | \end{rem} | ||
+ | \begin{proof} | ||
+ | Stačí z $G$ postupně odebírat hrany takové, že neklesne barevnost. | ||
+ | Jestliže už to nejde, máme $k$-kritický podgraf $G$. | ||
+ | \end{proof} | ||
+ | \begin{thm} | ||
+ | Nechť $G=(V,E)$ je $k$-kritický graf. Potom $\delta(G)\geq k-1$. | ||
+ | \end{thm} | ||
+ | \begin{proof} | ||
+ | Sporem: nechť $\left(\exists u\in V\right)\left(d_{G}(u)\leq k-2\right)$. | ||
+ | Potom z $u$ vede méně hran, než kolik je potřeba barev na obarvení | ||
+ | $G$, a to alespoň o $2$. Při každém vlastním obarvení není barva | ||
+ | $u$ určena jednoznačně. Odeberme tedy vrchol $u$. Z $k$-kritičnosti | ||
+ | $G$ lze zbytek grafu obarvit $k-1$ barvami. Jestliže nyní přidáme | ||
+ | vrchol $u$ zpět, lze dát vrcholu $u$ alespoň $2$ různé barvy z | ||
+ | dostupných $k$ barev. Proto nemusíme nutně vybrat novou ($k$-tou) | ||
+ | barvu a $G$ se nám podaří obarvit $k-1$ barvami, což je spor. | ||
+ | \end{proof} | ||
+ | \begin{defn} | ||
+ | Řekneme, že množina $S\subset V$ je \textbf{řezem} (angl. \emph{cut}) | ||
+ | v grafu $G=(V,E)$, jestliže pro počty komponent platí $c(G)<c(G\backslash S)$. | ||
+ | \end{defn} | ||
+ | \begin{rem*} | ||
+ | Když $S=\{ u\}$ je řez v souvislém grafu, pak graf musí vypadat jako | ||
+ | na obrázku \ref{cap:jednoprvkovy-rez-grafem}.% | ||
+ | \begin{figure} | ||
+ | \begin{center} | ||
+ | %Title: rez_grafem.fig | ||
+ | %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 | ||
+ | %%CreationDate: Thu Feb 12 19:29:04 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}\ellipticalarc axes ratio 0.356:0.356 360 degrees | ||
+ | from 2.737 23.218 center at 2.381 23.218 | ||
+ | }% | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.356:0.356 360 degrees | ||
+ | from 3.689 24.289 center at 3.334 24.289 | ||
+ | }% | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.356:0.356 360 degrees | ||
+ | from 2.737 25.241 center at 2.381 25.241 | ||
+ | }% | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 2.381 24.289 | ||
+ | }% | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.356:0.356 360 degrees | ||
+ | from 1.784 24.289 center at 1.429 24.289 | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | \setdashes < 0.1080cm> | ||
+ | {\color[rgb]{0,0,0}\plot 2.381 23.457 2.381 24.289 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\plot 3.095 24.289 2.381 24.289 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\plot 2.381 25.004 2.381 24.289 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\plot 1.666 24.289 2.381 24.289 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{3}$}% | ||
+ | } [lB] at 3.213 24.170 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{2}$}% | ||
+ | } [lB] at 2.142 25.121 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{1}$}% | ||
+ | } [lB] at 1.190 24.170 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{4}$}% | ||
+ | } [lB] at 2.142 23.097 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$u$}% | ||
+ | } [lB] at 2.024 23.933 | ||
+ | \linethickness=0pt | ||
+ | \putrectangle corners at 1.056 25.612 and 3.706 22.847 | ||
+ | \endpicture} | ||
+ | \end{center} | ||
+ | |||
+ | |||
+ | \caption{\label{cap:jednoprvkovy-rez-grafem}Jednoprvkový řez grafem} | ||
+ | \end{figure} | ||
+ | |||
+ | \end{rem*} | ||
+ | \begin{thm} | ||
+ | \label{thm:rez-neni-klika}Řez $k$-kritického grafu není klika. | ||
+ | \end{thm} | ||
+ | \begin{proof} | ||
+ | Sporem: nechť $G$ je $k$-kritický, $S$ je řez v $G$ a zároveň | ||
+ | klika v $G$. Předpokládejme, že $S=\{ v_{1},...,v_{r}\}$, tj. $\# S=r$. | ||
+ | Každé vlastní $k$-vrcholové obarvení musí přiřadit vrcholum z $S$ | ||
+ | $r$ různých barev. Nechť $G\backslash S=G_{1}\cup G_{2}\cup...\cup G_{s}$. | ||
+ | Potom vezmeme pro každé $i\in\hat{s}$ podgrafy $S\cup G_{i}$ (viz. | ||
+ | obrázek \ref{cap:rez-neni-klika}) a obarvíme je $k-1$ barvami tak, | ||
+ | aby barvy použité na vrcholech $S$ byly právě barvy $1,2,...,r$. | ||
+ | (Víme, že existuje vlastní $(k-1)$-vrcholové obarvení těchto podgrafů, | ||
+ | takže dodatečný požadavek lze zajistit jen vhodnou permutací barev.) | ||
+ | Jestliže nyní všechny takto obarvené komponenty sjednotíme, získáme | ||
+ | vlastní $(k-1)$-vrcholové obarvení grafu $G$, což je spor.% | ||
+ | \begin{figure} | ||
+ | \begin{center} | ||
+ | %Title: rez_neni_klika.fig | ||
+ | %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 | ||
+ | %%CreationDate: Thu Feb 12 19:36:40 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}\ellipticalarc axes ratio 0.356:0.356 360 degrees | ||
+ | from 2.737 22.979 center at 2.381 22.979 | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | \setdashes < 0.1080cm> | ||
+ | {\color[rgb]{0,0,0}\plot 2.381 23.218 2.381 24.052 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{4}$}% | ||
+ | } [lB] at 2.142 22.860 | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | \setsolid | ||
+ | {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.356:0.356 360 degrees | ||
+ | from 3.926 24.289 center at 3.571 24.289 | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | \setdashes < 0.1080cm> | ||
+ | {\color[rgb]{0,0,0}\plot 3.334 24.289 2.618 24.289 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{3}$}% | ||
+ | } [lB] at 3.452 24.170 | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | \setsolid | ||
+ | {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.356:0.356 360 degrees | ||
+ | from 2.737 25.480 center at 2.381 25.480 | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | \setdashes < 0.1080cm> | ||
+ | {\color[rgb]{0,0,0}\plot 2.381 25.241 2.381 24.528 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{2}$}% | ||
+ | } [lB] at 2.142 25.360 | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | \setsolid | ||
+ | {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.356:0.356 360 degrees | ||
+ | from 1.545 24.289 center at 1.190 24.289 | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | \setdashes < 0.1080cm> | ||
+ | {\color[rgb]{0,0,0}\plot 1.429 24.289 2.142 24.289 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{1}$}% | ||
+ | } [lB] at 0.950 24.170 | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | \setsolid | ||
+ | {\color[rgb]{0,0,0}\ellipticalarc axes ratio 1.130:0.624 360 degrees | ||
+ | from 2.915 24.289 center at 1.784 24.289 | ||
+ | }% | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.385:0.385 360 degrees | ||
+ | from 2.766 24.289 center at 2.381 24.289 | ||
+ | }% | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$S \cup G_{1}$}% | ||
+ | } [lB] at 0.237 23.336 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$S$}% | ||
+ | } [lB] at 2.261 24.170 | ||
+ | \linethickness=0pt | ||
+ | \putrectangle corners at 0.205 25.851 and 3.943 22.608 | ||
+ | \endpicture} | ||
+ | \end{center} | ||
+ | |||
+ | |||
+ | \caption{\label{cap:rez-neni-klika}K důkazu věty \ref{thm:rez-neni-klika}} | ||
+ | \end{figure} | ||
+ | |||
+ | \end{proof} | ||
+ | \begin{rem*} | ||
+ | V předchozím důkazu je skutečně důležité, aby $S$ byla klika. Pokud | ||
+ | budeme stejně postupovat v případě obecné $S$, může se stát, že vlastní | ||
+ | $(k-1)$-vrcholové obarvení podgrafů $S\cup G_{i}$ vynucuje, aby | ||
+ | některé prvky $S$ byly obarveny stejnou barvou, přičemž pro různá | ||
+ | $i\in\hat{s}$ se jedná o různé prvky. Nebude potom možné vhodně zpermutovat | ||
+ | barvy, aby vrcholy z $S$ měly stejnou barvu nezávisle na $i$. | ||
+ | \end{rem*} | ||
+ | |||
+ | \subsection{Brooksova věta} | ||
+ | |||
+ | \begin{lem} | ||
+ | Nechť $G$ je $k$-kritický graf s řezem $S=\{ u,v\}$. Potom platí\[ | ||
+ | d_{G}(u)+d_{G}(v)\geq3k-5.\] | ||
+ | |||
+ | \end{lem} | ||
+ | \begin{proof} | ||
+ | Než dokážeme samotnou nerovnost, připravíme si tři pomocná tvrzení. | ||
+ | Mějme při tom na paměti, že vrcholy $u,v$ nejsou podle předchozí | ||
+ | věty \ref{thm:rez-neni-klika} spojeny hranou. | ||
+ | |||
+ | \smallskip{} | ||
+ | \textbf{Tvrzení 1.} | ||
+ | |||
+ | \emph{Graf} $G\backslash\{ u,v\}$ \emph{(kde} $\{ u,v\}$ \emph{nemá | ||
+ | smysl hrany, ale množiny vrcholů odebírané z} $V(G)$) \emph{se skládá | ||
+ | z právě} $2$ \emph{komponent} $G_{1}=(V_{1},E_{1}),G_{2}=(V_{2},E_{2})$ | ||
+ | \emph{takových, že} | ||
+ | \begin{itemize} | ||
+ | \item \emph{Každé vlastní} $(k-1)$\emph{-vrcholové obarvení (vlastního) | ||
+ | indukovaného podgrafu} $A=G[V_{1}\cup\{ u,v\}]$ \emph{přiřazuje vrcholům} | ||
+ | $u,v$ \emph{stejnou barvu. (Jinými slovy: barvíme-li} $A$ \emph{pomocí} | ||
+ | $k-1$ \emph{barev, musíme dát} $u$ \emph{a} $v$ \emph{stejnou barvu)} | ||
+ | \item \emph{Každé vlastní} $(k-1)$\emph{-vrcholové obarvení (vlastního) | ||
+ | indukovaného podgrafu} $B=G[V_{2}\cup\{ u,v\}]$ \emph{přiřazuje vrcholům} | ||
+ | $u,v$ \emph{různou barvu.} | ||
+ | \end{itemize} | ||
+ | \hfill{} | ||
+ | \begin{center} | ||
+ | %Title: brooks_lemma1.fig | ||
+ | %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 | ||
+ | %%CreationDate: Thu Feb 12 19:36:16 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.191}}} at 10.478 19.215 | ||
+ | }% | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.191}}} at 10.478 19.840 | ||
+ | }% | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\ellipticalarc axes ratio 3.095:2.024 360 degrees | ||
+ | from 13.572 19.526 center at 10.478 19.526 | ||
+ | }% | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\ellipticalarc axes ratio 1.547:1.556 360 degrees | ||
+ | from 12.857 19.526 center at 11.309 19.526 | ||
+ | }% | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\ellipticalarc axes ratio 1.547:1.556 360 degrees | ||
+ | from 11.191 19.526 center at 9.644 19.526 | ||
+ | }% | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.595:0.931 360 degrees | ||
+ | from 9.525 19.526 center at 8.930 19.526 | ||
+ | }% | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.595:0.931 360 degrees | ||
+ | from 12.620 19.526 center at 12.025 19.526 | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | \setdashes < 0.1080cm> | ||
+ | {\color[rgb]{0,0,0}\plot 10.478 19.215 11.667 19.215 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\plot 10.478 19.215 9.286 19.215 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\plot 10.478 19.840 11.667 19.840 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\plot 10.478 19.840 9.286 19.840 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G$}% | ||
+ | } [lB] at 10.240 17.659 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$B$}% | ||
+ | } [lB] at 11.311 18.282 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$A$}% | ||
+ | } [lB] at 9.404 18.282 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{2}$}% | ||
+ | } [lB] at 11.906 19.450 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{1}$}% | ||
+ | } [lB] at 8.572 19.450 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v$}% | ||
+ | } [lB] at 10.357 18.707 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$u$}% | ||
+ | } [lB] at 10.357 20.151 | ||
+ | \linethickness=0pt | ||
+ | \putrectangle corners at 7.366 21.565 and 13.589 17.471 | ||
+ | \endpicture} | ||
+ | \end{center} | ||
+ | \hfill{} | ||
+ | |||
+ | \emph{Důkaz tvrzení 1:} | ||
+ | |||
+ | Zpočátku nevíme, zda $G\backslash\{ u,v\}$ obsahuje \emph{jen} dvě | ||
+ | komponenty. Lze však tvrdit, že $G\backslash\{ u,v\}$ musí obsahovat | ||
+ | alespoň jednu komponentu s vlastností komponenty $G_{1}$. Kdyby to | ||
+ | tak nebylo, mohli bychom každý podgraf grafu $G$ indukovaný vrcholy | ||
+ | jedné z komponent a vrcholy $u,v$ obarvit $k-1$ barvami tak, že | ||
+ | $u$ a $v$ by měly různé barvy. Potom bychom barvy zpermutovali tak, | ||
+ | aby $u,v$ měly vždy barvy $1,2$. Takto obarvené podgrafy bychom | ||
+ | sjednotili a získali tak celý graf $G$ obarvený $k-1$ barvami, což | ||
+ | je spor. | ||
+ | |||
+ | Ze stejného důvodu obsahuje $G\backslash\{ u,v\}$ alespoň jednu komponentu | ||
+ | s vlastností $G_{2}$. Nyní si tyto komponenty označíme přímo jako | ||
+ | $G_{1}$ a $G_{2}$. Ukážeme, že žádné jiné komponenty už v $G\backslash\{ u,v\}$ | ||
+ | neexistují: Indukovaný podgraf $A\cup B=G[V_{1}\cup V_{2}\cup\{ u,v\}]$ | ||
+ | podle vlastností komponent $G_{1}$ a $G_{2}$ nejde (vlastním obarvením) | ||
+ | obarvit $k-1$ barvami, protože vrcholy $u,v$ nemohou mít současně | ||
+ | podle $G_{1}$ stejnou a podle $G_{2}$ různou barvu. Proto $\chi(A\cup B)=k$. | ||
+ | Protože $G$ je $k$-kritický, musí platit $G=A\cup B$. | ||
+ | |||
+ | \smallskip{} | ||
+ | \textbf{Tvrzení 2.} | ||
+ | |||
+ | \emph{Podgraf} $C=A\cup\{\{ u,v\}\}$\emph{, který vznikne přidáním | ||
+ | hrany} $\{ u,v\}$ \emph{do} $A$\emph{, je již} $k$\emph{-kritický.} | ||
+ | |||
+ | \hfill{} | ||
+ | \begin{center} | ||
+ | %Title: brooks_lemma2.fig | ||
+ | %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 | ||
+ | %%CreationDate: Thu Feb 12 19:23: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.191}}} at 10.478 19.215 | ||
+ | }% | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.191}}} at 10.478 19.840 | ||
+ | }% | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\ellipticalarc axes ratio 1.547:1.556 360 degrees | ||
+ | from 11.191 19.526 center at 9.644 19.526 | ||
+ | }% | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.595:0.931 360 degrees | ||
+ | from 9.525 19.526 center at 8.930 19.526 | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness=1pt | ||
+ | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
+ | {\color[rgb]{0,0,0}\putrule from 10.478 19.884 to 10.478 19.171 | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | \setdashes < 0.1080cm> | ||
+ | {\color[rgb]{0,0,0}\plot 10.478 19.215 9.286 19.215 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\plot 10.478 19.840 9.286 19.840 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$C$}% | ||
+ | } [lB] at 9.404 18.282 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{1}$}% | ||
+ | } [lB] at 8.572 19.450 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v$}% | ||
+ | } [lB] at 10.357 18.707 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$u$}% | ||
+ | } [lB] at 10.357 20.151 | ||
+ | \linethickness=0pt | ||
+ | \putrectangle corners at 8.079 21.099 and 11.208 17.954 | ||
+ | \endpicture} | ||
+ | \end{center} | ||
+ | \hfill{} | ||
+ | |||
+ | \emph{Důkaz tvrzení 2:} | ||
+ | |||
+ | Zřejmě platí $\chi(C)=k$, protože $A$ lze obarvit $k-1$ barvami | ||
+ | jen tak, že $u,v$ mají stejnou barvu. Když je tedy spojíme hranou, | ||
+ | tak už to nejde. | ||
+ | |||
+ | Ubereme-li z $G$ libovolnou hranu, lze jej obarvit $k-1$ barvami. | ||
+ | Pokud navíc tato hrana leží v podgrafu $A$, zůstává ve výsledném | ||
+ | grafu celý podgraf $B$, takže v uvedeném vlastním obarvení musí mít | ||
+ | $u,v$ různou barvu. Proto nezáleží na tom, zda je navíc spojíme hranou. | ||
+ | Tím jsme dokázali, že po ubrání čehokoliv z $C$ vznikne graf s barevností | ||
+ | $k-1$, takže $C$ je $k$-kritický. | ||
+ | |||
+ | \smallskip{} | ||
+ | \textbf{Tvrzení 3.} | ||
+ | |||
+ | \emph{Označme jako} $D$ \emph{graf, který vznikne z grafu} $B$ \emph{sloučením | ||
+ | vrcholů} $u,v$ \emph{do nového vrcholu} $w$. \emph{Potom} $D$ \emph{je} | ||
+ | $k$\emph{-kritický.} | ||
+ | |||
+ | \hfill{} | ||
+ | \begin{center} | ||
+ | %Title: brooks_lemma3.fig | ||
+ | %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 | ||
+ | %%CreationDate: Thu Feb 12 19:17: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}\ellipticalarc axes ratio 0.595:0.931 360 degrees | ||
+ | from 3.332 25.123 center at 2.737 25.123 | ||
+ | }% | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\ellipticalarc axes ratio 1.547:1.556 360 degrees | ||
+ | from 3.569 25.123 center at 2.021 25.123 | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | \setdashes < 0.1080cm> | ||
+ | {\color[rgb]{0,0,0}\plot 1.190 25.123 2.379 25.436 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\plot 1.190 25.123 2.379 24.812 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$D$}% | ||
+ | } [lB] at 2.024 23.878 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$w$}% | ||
+ | } [lB] at 1.010 25.449 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{2}$}% | ||
+ | } [lB] at 2.618 25.047 | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | \setsolid | ||
+ | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.191}}} at 1.190 25.123 | ||
+ | }% | ||
+ | \linethickness=0pt | ||
+ | \putrectangle corners at 0.457 26.695 and 3.586 23.550 | ||
+ | \endpicture} | ||
+ | \end{center} | ||
+ | \hfill{} | ||
+ | |||
+ | \emph{Důkaz tvrzení 3:} | ||
+ | |||
+ | Analogicky jako tvrzení 2. $\chi(D)=k$, neboť $B$ lze obarvit $k-1$ | ||
+ | barvami, jen když $u,v$ mají různou barvu. Jejich spojením do $w$ | ||
+ | však vynucujeme stejnou. | ||
+ | |||
+ | Ubereme-li z $G$ libovolnou hranu, lze jej obarvit $k-1$ barvami. | ||
+ | Pokud navíc tato hrana leží v podgrafu $B$, zůstává ve výsledném | ||
+ | grafu celý podgraf $A$, takže v uvedeném vlastním obarvení musí mít | ||
+ | $u,v$ stejnou barvu. Proto (z hlediska obarvení) nezáleží na tom, | ||
+ | zda je navíc sloučíme do $w$. Tím jsme dokázali, že po ubrání čehokoliv | ||
+ | z $D$ vznikne graf s barevností $k-1$, takže $D$ je $k$-kritický. | ||
+ | |||
+ | \smallskip{} | ||
+ | Nyní konečně můžeme dokázat uvedenou nerovnost. Zřejmě platí následující | ||
+ | vztahy:\begin{eqnarray*} | ||
+ | d_{G}(u) & = & d_{A}(u)+d_{B}(u),\\ | ||
+ | d_{G}(v) & = & d_{A}(v)+d_{B}(v),\\ | ||
+ | d_{C}(u) & = & d_{A}(u)+1,\\ | ||
+ | d_{C}(v) & = & d_{A}(v)+1,\\ | ||
+ | d_{D}(w) & = & d_{B}(u)+d_{B}(v).\end{eqnarray*} | ||
+ | Protože v $k$-kritickém grafu platí $\delta\geq k-1$, dostáváme\[ | ||
+ | d_{G}(u)+d_{G}(v)=d_{A}(u)+d_{B}(u)+d_{A}(v)+d_{B}(v)=\] | ||
+ | \[ | ||
+ | =\underbrace{d_{C}(u)}_{\geq k-1}+\underbrace{d_{C}(v)}_{\geq k-1}-2+\underbrace{d_{D}(w)}_{\geq k-1}\geq3k-5.\] | ||
+ | |||
+ | \end{proof} | ||
+ | \begin{thm} | ||
+ | \textbf{\emph{(Brooks)}} | ||
+ | |||
+ | Nechť $G$ je souvislý graf , a přitom $G$ není ani klika ani kružnice | ||
+ | liché délky. Potom $\chi(G)\leq\Delta(G)$. | ||
+ | \end{thm} | ||
+ | \begin{rem*} | ||
+ | Velmi snadno jsme již dokázali, že pro každý graf platí $\chi(G)\leq\Delta(G)+1$. | ||
+ | Nyní bude důkaz obtížnější. | ||
+ | \end{rem*} | ||
+ | \begin{proof} | ||
+ | Nejprve ukážeme, že BÚNO lze důkaz provést pouze pro $k$-kritické | ||
+ | grafy. Mějme tedy souvislý graf, ani kliku ani lichou kružnici, který | ||
+ | navíc \emph{není} $k$-kritický. Potom najdeme jeho vlastní $k$-kritický | ||
+ | podgraf $H$. Platí tedy $\chi(H)=\chi(G)=k$ a zřejmě též $\Delta(H)\leq\Delta(G)$. | ||
+ | Mohou nastat následující možnosti: | ||
+ | \begin{enumerate} | ||
+ | \item $H$ není klika ani lichá kružnice. Potom použijeme naše tvrzení dokázané | ||
+ | pro $k$-kritické grafy: $\chi(H)\leq\Delta(H)$. Z toho plyne\[ | ||
+ | \chi(G)=\chi(H)\leq\Delta(H)=\Delta(G).\] | ||
+ | |||
+ | \item $H$ je klika. Naše tvrzení použít nemůžeme, zato je nyní zřejmě $\Delta(H)<\Delta(G)$, | ||
+ | protože $H$ je vlastním podgrafem souvislého grafu $G$. Protože | ||
+ | pro libovolný graf $\tilde{G}$ platí $\chi(\tilde{G})\leq\Delta(\tilde{G})+1$, | ||
+ | tak\[ | ||
+ | \chi(G)=\chi(H)\leq\Delta(H)+1\leq\Delta(G).\] | ||
+ | |||
+ | \item $H$ je lichá kružnice. Zde je zdůvodnění obdobné tomu v předchozím | ||
+ | bodě: Každý vrchol grafu $H$ má stupeň $2$ a tak $\Delta(H)=2$. | ||
+ | Protože ale $G$ je souvislý a $H$ je vlastním podgrafem $G$, tak | ||
+ | v $G$ musí být na nějaký vrchol z kružnice $H$ napojena alespoň | ||
+ | jedna další hrana. To opět znamená $\Delta(H)<\Delta(G)$, zbytek | ||
+ | je stejný. | ||
+ | \end{enumerate} | ||
+ | Nyní dokážeme samotné tvrzení pouze pro $k$-kritické grafy, které | ||
+ | ovšem budeme označovat opět jako ,,$G${}``. Platí tedy $k=\chi(G)$. | ||
+ | Podle poznámky \ref{rem:123kriticke-grafy} je zřejmé, že $k\geq4$, | ||
+ | protože jinak by nebyly splněny předpoklady věty. Mohou nastat dvě | ||
+ | možnosti: | ||
+ | |||
+ | \bigskip{} | ||
+ | \textbf{a)} Nechť v $G$ existuje řez $S=\{ u,v\}$. Potom podle předchozí | ||
+ | věty platí\[ | ||
+ | 2\Delta(G)\geq d_{G}(u)+d_{G}(v)\geq3k-5=2k-1+\underbrace{k-4}_{\geq0}\geq2k-1.\] | ||
+ | Na levé straně nerovnosti však máme sudé číslo a na pravé straně je | ||
+ | liché číslo. Proto samozřejmě musí platit i $2\Delta(G)\geq2k$, neboli\[ | ||
+ | \Delta(G)\geq k=\chi(G).\] | ||
+ | |||
+ | |||
+ | \bigskip{} | ||
+ | \textbf{b)} Nechť v $G$ neexistuje dvouprvkový řez. To znamená, že | ||
+ | po odebrání libovolných dvou vrcholů $u,v$ zůstává graf $G\backslash\{ u,v\}$ | ||
+ | souvislý. Z předpokladu ,,$G$ není klika{}`` najdeme v $G$ vrcholy | ||
+ | $u,v$, které nejsou spojeny hranou, takže jejich vzdálenost $d(u,v)\geq2$. | ||
+ | Tím pádem najdeme $u,v$ i tak, že $d(u,v)=2$. Označme jako $w$ | ||
+ | vrchol, přes který jsou spojeny. | ||
+ | |||
+ | \hfill{} | ||
+ | \begin{center} | ||
+ | %Title: brooks_uvw.fig | ||
+ | %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 | ||
+ | %%CreationDate: Thu Feb 12 18:00:48 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 7.620 20.955 | ||
+ | }% | ||
+ | % | ||
+ | % Fig POLYLINE object | ||
+ | % | ||
+ | \linethickness=1pt | ||
+ | \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) | ||
+ | {\color[rgb]{0,0,0}\plot 7.620 20.955 9.049 20.479 / | ||
+ | \plot 9.049 20.479 7.620 20.003 / | ||
+ | }% | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}w}% | ||
+ | } [lB] at 9.404 20.360 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}v}% | ||
+ | } [lB] at 7.023 19.884 | ||
+ | % | ||
+ | % Fig TEXT object | ||
+ | % | ||
+ | \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}u}% | ||
+ | } [lB] at 7.023 20.836 | ||
+ | % | ||
+ | % Fig ELLIPSE | ||
+ | % | ||
+ | \linethickness= 0.500pt | ||
+ | \setplotsymbol ({\thinlinefont .}) | ||
+ | {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.049 20.479 | ||
+ | }% | ||
+ | \linethickness=0pt | ||
+ | \putrectangle corners at 6.991 21.433 and 9.436 19.852 | ||
+ | \endpicture} | ||
+ | \end{center} | ||
+ | \hfill{} | ||
+ | |||
+ | Nyní očíslujeme vrcholy grafu $G$ speciálním způsobem. | ||
+ | \begin{itemize} | ||
+ | \item Označíme $v_{1}=u,v_{2}=v,v_{n}=w$. | ||
+ | \item $v_{3},v_{4},v_{5},...,v_{n}=w$ budou vrcholy grafu $G\backslash\{ u,v\}$ | ||
+ | uspořádané tak, že\[ | ||
+ | \left(\forall i\in\{3,4,...,n-1\}\right)\left(\exists j>i\right)\left(\{ v_{i},v_{j}\}\in E\right),\] | ||
+ | neboli z každého vrcholu $v_{3},v_{4},v_{5},...,v_{n-1}$ vede v grafu | ||
+ | $G\backslash\{ u,v\}$ hrana do nějakého vrcholu, který je v uspořádání | ||
+ | až za ním. Takové uspořádání vznikne například tak, že vrcholy $v_{3},v_{4},v_{5},...,v_{n}$ | ||
+ | seřadíme sestupně podle jejich vzdálenosti od vrcholu $w$ v grafu | ||
+ | $G\backslash\{ u,v\}$, tj. budou splňovat\[ | ||
+ | \left(\forall i,j\in\{3,4,...,n\}\right)\left(i<j\Rightarrow d_{G\backslash\{ u,v\}}(v_{i},w\}\geq d_{G\backslash\{ u,v\}}(v_{j},w\}\right).\] | ||
+ | V tom případě zřejmě $v_{n}=w$. | ||
+ | \end{itemize} | ||
+ | Takto uspořádané vrcholy $v_{1},...,v_{n}$ grafu $G$ už lze obarvit | ||
+ | nejvýše $\Delta(G)$ barvami, a to takto: | ||
+ | \begin{itemize} | ||
+ | \item Vrcholy $v_{1}=u,v_{2}=v$ dostanou barvu $1$, což je možné, neboť | ||
+ | spolu nesousedí. | ||
+ | \item Vrcholy $v_{3},v_{4},...,v_{n-1}$ obarvujeme postupně první barvou, | ||
+ | kterou je možné použít. Protože z každého z nich vede hrana do ještě | ||
+ | neobarvených vrcholů, má každý z nich ve chvíli, když na něj přijde | ||
+ | řada, nejvýše $\Delta(G)-1$ již obarvených sousedů, a tak existuje | ||
+ | barva $b\in\{1,2,...,\Delta(G)\}$, kterou jej lze obarvit. | ||
+ | \item Vrchol $v_{n}=w$ sousedí s vrcholy $u,v$, které mají oba barvu $1$, | ||
+ | a dále s nejvýše $\Delta(G)-2$ dalšími vrcholy, které mají nejvýše | ||
+ | $\Delta(G)-2$ různých barev. Celkem tedy sousedí s nejvýše $\Delta(G)$ | ||
+ | vrcholy, které mají nejvýše $\Delta(G)-1$ různých barev, a tak jej | ||
+ | lze také obarvit. | ||
+ | \end{itemize} | ||
+ | \end{proof} |
Aktuální verze z 15. 1. 2012, 13:52
[ 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 | popis | 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{Vrcholové obarvení grafu} \begin{defn} Nechť $G=(V,E)$ je graf, $k\in\N$. $k$-\textbf{vrcholovým obarvením} (angl. $k$\emph{-vertex colouring}) grafu $G$ nazveme zobrazení $\varphi:V\mapsto\hat{k}$. $\varphi$ se nazývá \textbf{vlastní} (angl. \emph{proper}) $k$-vrcholové obarvení grafu $G$, jestliže platí\[ \left(\forall u,v\in V\right)\left(\varphi(u)=\varphi(v)\Rightarrow\{ u,v\}\notin E\right),\] tj. jestliže stejně barevné vrcholy nejsou spojeny hranou. Minimální $k$ takové, že existuje $k$-vrcholové vlastní obarvení grafu $G$, se nazývá \textbf{barevnost} (angl. \emph{chromatic number}) grafu $G$ a značí se $\chi(G)$. \end{defn} \begin{example*} Jestliže vrcholy reprezentují účastníky reality show a hrany vedou mezi těmi, kteří se nesnášejí, pak $\chi(G)$ je minimální počet skupin, do nichž lze soutěžící rozdělit tak, aby v žádné skupině nebyli dva, kteří se nesnášejí. \end{example*} \begin{rem*} ~ \begin{itemize} \item $\chi(G)=1$ $\Leftrightarrow$ $G=(V,\emptyset)$. \item $\chi(G)=2$ $\Leftrightarrow$ $G$ je bipartitní s alespoň jednou hranou ($\Leftrightarrow$ v $G$ není kružnice liché délky). \item $\chi(G)=p,p\geq3$ $\Leftrightarrow$ ?? \end{itemize} Rozhodnout o tom, zda $\chi(G)=p$, je pro obecný graf NP-úplná úloha. Podle předchozích bodů můžeme jen ověřit, jestli $\chi(G)\geq3$ nebo ne. \end{rem*} \begin{rem} Zřejmě vždy platí $\chi(G)\leq n=\# V$. Jestliže obarvíme každý vrchol jinou barvou, dostaneme vlastní obarvení. Přitom když $G=K_{n}$, tj. je-li $G$ úplným grafem na $n$ vrcholech, tak $\chi(G)=n$. Platí i opačná implikace, protože chybí-li mezi dvěma vrcholy hrana, lze je obarvit stejnou barvou a zbylé vrcholy opět obarvit různě. Celkem tedy\[ \chi(G)=n\Leftrightarrow G=K_{n}.\] \end{rem} \begin{defn} \label{def:klika-nez-mnozina}Nechť $G=(V,E)$ je graf, $k\in\N$. \begin{itemize} \item \textbf{Klikou} (angl. \emph{clique}) velikosti $k$ v $G$ rozumíme množinu vrcholů $S\subset V$ takovou, že podgraf $G[S]=\left(S,E\cap\binom{S}{2}\right)$ indukovaný množinou $S$ je úplný, tj. každé dva vrcholy z $S$ jsou spojeny hranou v $G$. \item $S\subset V$ se nazývá \textbf{nezávislá množina} (angl. \emph{independent set}) velikosti $k$ v $G$, jestliže $E\cap\binom{S}{2}=\emptyset$, tj. jestliže žádné dva vrcholy z $S$ nejsou spojeny hranou v grafu $G$. \item $S\subset V$ se nazývá \textbf{vrcholové pokrytí} (angl. \emph{covering}) grafu $G$, jestliže $\left(\forall e\in E\right)\left(\exists v\in S\right)\left(v\in e\right)$, tj. jestliže každá hrana v $G$ má alespoň jeden konec v $S$. \end{itemize} Maximální velikost kliky v grafu $G$ značíme $\omega(G)$, maximální velikost nezávislé množiny značíme $\alpha(G)$. \end{defn} \begin{rem*} V přednášce někdy klikou velikosti $k$ nazýváme též úplný podgraf $K_{k}=G[S]$, který množina $S$ indukuje. \end{rem*} \begin{rem} \label{rem:alfa-omega-v-doplnku-G}Je-li $S$ nezávislá množina v $G$, pak $S$ je klika v $\bar{G}$ a naopak. Proto zřejmě platí\begin{eqnarray*} \alpha(\bar{G}) & = & \omega(G)\\ \omega(\bar{G)} & = & \alpha(G).\end{eqnarray*} \end{rem} \begin{rem*} Klikami a nezávislými množinami se budeme v různých souvislostech zabývat především v druhé části přednášky. Nyní tuto definici budeme potřebovat jen na několika málo místech. \end{rem*} \begin{rem*} Nechť $\varphi$ je vlastní $\chi(G)$-vrcholové obarvení grafu $G=(V,E)$, $i\in\widehat{\chi(G)}$. Potom mezi vrcholy z $\varphi^{-1}(i)$ nevede hrana, neboli $\varphi^{-1}(i)$ je nezávislá množina. Tím pádem\[ \#\varphi^{-1}(i)\leq\alpha(G)\] a přitom platí\[ \bigcup_{i=1}^{\chi(G)}\#\varphi^{-1}(i)=V.\] \end{rem*} \begin{thm} Nechť $G=(V,E)$ je graf. Potom platí\begin{eqnarray*} \# V & \leq & \alpha(G)\cdot\chi(G)\\ \omega(G) & \leq & \chi(G).\end{eqnarray*} \end{thm} \begin{proof} První tvrzení plyne okamžitě z předchozí poznámky. Druhé tvrzení je zřejmé: V $G$ existuje klika velikosti $\omega(G)$, jejíž vrcholy musí mít při vlastním obarvení grafu $G$ $\omega(G)$ různých barev. \end{proof} \begin{rem*} ~ \begin{enumerate} \item Jestliže $H\subset G$, potom $\chi(H)\leq\chi(G)$. \item Platí-li $G=G_{1}\cup G_{2}\cup...\cup G_{r}$, kde $G_{i}$ jsou komponenty grafu $G$, potom zřejmě\[ \chi(G)=\max_{i\in\hat{r}}\chi(G_{i}).\] \end{enumerate} \end{rem*} \begin{thm} Nechť $G=(V,E)$ je graf. Potom $\chi(G)\leq\Delta(G)+1$. \end{thm} \begin{proof} Tvrzení je formálně shodné s Vizingovou větou \ref{thm:Vizing} pro hranovou barevnost. Zde je však důkaz snadný. ,,Poctivě{}`` jej lze provést indukcí podle $n=\# V$. Pro $n=1$ je to jasné: $\Delta(G)=0$, $\chi(G)=1=\Delta(G)+1$. Indukční krok $n-1\to n$: V $G$ najdeme vrchol $u\in V$ takový, že $d_{G}(u)=\Delta(G)$. Samozřejmě je $\Delta(G\backslash u)\leq\Delta(G)$. Z indukčního předpokladu je $\chi(G\backslash u)\leq\Delta(G\backslash u)+1\leq\Delta(G)+1$. Najdeme tedy vlastní obarvení grafu $G\backslash u$ pomocí $\Delta(G)+1$ barev. Pokud nyní přidáme zpět vrchol $u$, který má $\Delta(G)$ sousedů, bude možné jej rovněž obarvit jednou z $\Delta(G)+1$ barev. Celý $G$ je tak obarven pomocí $\Delta(G)+1$ barev. \end{proof} \begin{rem*} Myšlenku předchozího důkazu lze shrnout jednoduše: Postupně barvíme jeden vrchol za druhým první dostupnou barvou. Nikdy se nemůže stát, že bychom neměli k dispozici žádnou volnou barvu, protože každý vrchol má méně sousedů, než kolik máme barev. \end{rem*} \begin{rem*} Dolní odhad na $\chi(G)$ není možné pomocí $\Delta(G)$ nijak vyjádřit: \begin{itemize} \item Úplný graf $K_{n}$ na $n$ vrcholech má $\chi(K_{n})=n=\Delta(G)+1$. \item Úplný bipartitní graf na $1+(n-1)$ vrcholech, tj. graf $S_{n-1}$ (viz definice \ref{def:specialni-grafy}) má $\Delta(S_{n-1})=n-1$, ale $\chi(G)=2$. \end{itemize} \end{rem*} \begin{thm} \label{thm:barevnost-s-doplnkem}Pro každý graf $G=(V,E)$ platí: \begin{enumerate} \item $\chi(G)+\chi(\bar{G})\leq n+1$, \item $\chi(G)\cdot\chi(\bar{G})\geq n$. \end{enumerate} \end{thm} Připravíme si dvě pomocná tvrzení, z nichž již plynou jednotlivé nerovnosti. \begin{lem} Buďte $G_{1}=(V_{1},E_{1}),G_{2}=(V_{2},E_{2})$ dva grafy. Potom platí\[ \chi(G_{1}\cup G_{2})\leq\chi(G_{1})\cdot\chi(G_{2}).\] \end{lem} \begin{proof} Zřejmě platí $\chi(G_{1})=\chi(\tilde{G}_{1})$, kde $\tilde{G}_{1}=(V_{1}\cup V_{2},E_{1})$, a stejně $\chi(G_{2})=\chi(\tilde{G}_{2})$, kde $\tilde{G}_{2}=(V_{1}\cup V_{2},E_{2})$. BÚNO je proto možné předpokládat $V_{1}=V_{2}(:=V)$. Z předpokladu existují obarvení grafů $G_{1}$ a $G_{2}$\begin{eqnarray*} \varphi_{1} & : & V\mapsto\left\{ 1,2,...,\chi(G_{1})\right\} ,\\ \varphi_{2} & : & V\mapsto\left\{ 1,2,...,\chi(G_{2})\right\} .\end{eqnarray*} Najdeme obarvení grafu $G_{1}\cup G_{2}$ pomocí $\chi(G_{1})\cdot\chi(G_{2})$ barev. Definujme nyní pro každé $v\in V$\[ \psi(v)=\left(\varphi_{1}(v),\varphi_{2}(v)\right).\] Potom pro každé $u,v\in V$ platí $\left(\psi(u)=\psi(v)\right)$$\Rightarrow$$\left(\varphi_{1}(u)=\varphi_{1}(v)\wedge\varphi_{2}(u)=\varphi_{2}(v)\right)$$\Rightarrow$\\ $\Rightarrow$$\left(\{ u,v\}\notin E_{1}\wedge\{ u,v\}\notin E_{2}\right)$$\Rightarrow$$\{ u,v\}\notin E_{1}\cup E_{2}$. Zobrazení $\psi$ je\[ \psi:V\mapsto\left\{ 1,2,...,\chi(G_{1})\right\} \times\left\{ 1,2,...,\chi(G_{2})\right\} .\] Obor hodnot zobrazení $\psi$ je však (množinově) izomorfní s množinou $\left\{ 1,2,...,\chi(G_{1})\cdot\chi(G_{2})\right\} $. Abychom korektně definovali vrcholové obarvení grafu $G_{1}\cup G_{2}$, označme \[ B:\left\{ 1,2,...,\chi(G_{1})\right\} \times\left\{ 1,2,...,\chi(G_{2})\right\} \mapsto\left\{ 1,2,...,\chi(G_{1})\cdot\chi(G_{2})\right\} \] bijekci mezi uvedenými množinami. Potom lze pro každé $v\in V$ definovat $\chi(G_{1})\cdot\chi(G_{2})$-vrcholové obarvení grafu $G_{1}\cup G_{2}$ takto:\[ \varphi(v)=B(\psi(v)).\] Pro $\varphi$ platí $\left(\forall u,v\in V\right)\left(\varphi(u)=\varphi(v)\Rightarrow\{ u,v\}\notin E_{1}\cup E_{2}\right)$, takže se skutečně jedná o vrcholové obarvení. \end{proof} \begin{cor*} Platí tvrzení $(2)$ věty \ref{thm:barevnost-s-doplnkem}. \end{cor*} \begin{proof} Protože $G\cup\bar{G}=K_{n}$, tak\[ n=\chi(K_{n})=\chi(G\cup\bar{G})\leq\chi(G)\cdot\chi(\bar{G}).\] \end{proof} \begin{lem} Buď $G=(V,E)$ graf. Nechť existuje disjunktní rozklad množiny vrcholů $V=V_{1}\cup V_{2}\cup...\cup V_{k}$ takový, že\[ \left(\forall i,j\in\hat{k},i\neq j\right)\left(\exists u\in V_{i}\right)\left(\exists v\in V_{j}\right)\left(\{ u,v\}\notin E\right).\] Potom $\chi(G)\leq n+1-k$. \end{lem} \begin{proof} Indukcí podle $k$. Pro $k=1$ máme $\chi(G)\leq n+1-1=n$, což je pravda. Indukční krok $k-1\to k$: Platí $\chi(G\backslash V_{k})=\left(n-\# V_{k}\right)+1-(k-1)=\left(n-\# V_{k}\right)+2-k$. Nyní vezmeme $\# V_{k}$ nových barev a obarvíme vrcholy z $V_{k}$ těmito barvami, každý vrchol jinou barvou. Máme tak obarvený celý graf, a to $\leq\left(n-\# V_{k}\right)+2-k+\# V_{k}=n+2-k$ barvami. Pokud je tento počet barev $\leq n+1-k$, je hotovo. Jestliže je použito právě $n+2-k$ barev, musíme pokračovat a obarvení upravit. Z předpokladu platí\[ \left(\forall i\in\{1,2,...,k-1\}\right)\left(\exists x_{i}\in V_{i}\right)\left(\exists y_{i}\in V_{k}\right)\left(\{ x_{i},y_{i}\}\notin E\right).\] Množina $V\backslash\{ x_{1},x_{2},...,x_{k-1}\}$ má počet vrcholů $n-(k-1)=n+1-k$, což je méně, než počet použitých barev. Proto existuje barva $b$, která se vyskytuje pouze na vrcholech $x_{1},x_{2},...,x_{k-1}$. Této barvy se zbavíme tak, že každý vrchol $x_{i}$ ($i\in\{1,...,k-1\}$), který má barvu $b$, přebarvíme na barvu vrcholu $y_{i}$. Potom nové obarvení je stále vlastní. $\{ x_{i},y_{i}\}$ totiž nejsou v hraně, a i kdyby různým $x_{i},x_{j}$ příslušel stejný vrchol $y_{i}=y_{j}$, potom, protože oba vrcholy $x_{i},x_{j}$ měly stejnou barvu $b$, lze je opět obarvit stejnou barvou - barvou vrcholu $y_{i}$. \end{proof} \begin{cor*} Platí tvrzení $(1)$ věty \ref{thm:barevnost-s-doplnkem}. \end{cor*} \begin{proof} Označme $k=\chi(G)$. Nechť $\varphi$ je vlastní $k$-vrcholové obarvení $G$. Pro každé $i\in\hat{k}$ označme\[ V_{i}:=\varphi^{-1}(i).\] Potom platí, že \begin{equation} \left(\forall i,j\in\hat{k},1\leq i\leq j\leq k\right)\left(\exists u\in V_{i}\right)\left(\exists v\in V_{j}\right)\left(\{ u,v\}\in E\right).\label{eq:hranaViVj}\end{equation} Kdyby tomu tak nebylo, tj. kdyby\[ \left(\exists i,j\in\hat{k},1\leq i\leq j\leq k\right)\left(\forall u\in V_{i}\right)\left(\forall v\in V_{j}\right)\left(\{ u,v\}\notin E\right),\] bylo by možné vrcholy z $V_{i}$ i z $V_{j}$ obarvit stejnou barvou, a tak by $\chi(G)<k$, což je spor. Vezměme nyní graf $\bar{G}$ a definujme na něm stejný rozklad $V=\bigcup_{i=1}^{k}V_{i}$. Potom z (\ref{eq:hranaViVj}) vznikne pro graf $\bar{G}$ přímo předpoklad lemmatu. Proto\[ \chi(\bar{G})\leq n+1-k=n+1-\chi(G),\] což už je první tvrzení věty \ref{thm:barevnost-s-doplnkem}. \end{proof} \subsection{$k$-kritické grafy} \begin{defn} Řekneme, že graf $G=(V,E)$ je $k$-\textbf{kritický}, jestliže $\chi(G)=k$ a pro každý vlastní podgraf $H\subsetneqq G$ je $\chi(H)<\chi(G)$. \end{defn} \begin{obs} $k$-kritický graf je souvislý. \end{obs} \begin{proof} Víme, že má-li $G$ komponenty $G_{1},...,G_{r}$, tak potom\[ \chi(G)=\max_{i\in\hat{r}}\chi(G_{i}).\] Je-li $r\geq2$, existuje jedna nebo více komponent, které lze z grafu $G$ odebrat, aniž se sníží jeho barevnost. Proto takový $G$ není $k$-kritický. \end{proof} \begin{rem} \label{rem:123kriticke-grafy}~ \begin{itemize} \item $1$-kritický graf je $G=\{\{ v\},\emptyset\}$. \item $2$-kritický graf je $G=\{\{ u,v\},\{\{ u,v\}\}\}$. \item $3$-kritický graf je $C_{2n-1}$ (kružnice liché délky). \end{itemize} \end{rem} \begin{proof} První dvě tvrzení jsou zřejmá. Dále víme, že $\chi(G)=2$, právě když $G$ je bipartitní graf. $3$-kritický graf tedy nesmí být bipartitní, ale odebráním čehokoliv z něj musí bipartitní graf vzniknout. Jediný graf, který to splňuje, je kružnice liché délky bez dalších odboček. \end{proof} \begin{rem*} $4$-kritický graf vidíme na obrázku \ref{cap:4kriticky-graf}. Odebereme-li totiž hranu z obvodu, lze vrcholy po obvodě obarvit jen barvami $1$ a $2$ a vrchol uprostřed barvou $3$. Odebereme-li hranu vedoucí do středu, obarvíme vrcholy po obvodu kromě vrcholu $v_{0}$, ze kterého jsme odebrali hranu, barvami $1$ a $2$. Vrchol $v_{0}$ a střed pak obarvíme barvou $3$.% \begin{figure} \begin{center} %Title: 4kriticky.fig %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 %%CreationDate: Thu Feb 12 19:45:28 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 8.333 18.098 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 8.096 19.050 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 8.333 20.003 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.954 19.765 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 10.954 18.337 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.525 17.621 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.525 20.479 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.525 19.050 }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\putrule from 8.096 19.050 to 9.525 19.050 }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\putrule from 9.525 17.621 to 9.525 19.050 \plot 9.525 19.050 8.333 18.098 / }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\plot 10.954 19.765 9.525 19.050 / \plot 9.525 19.050 10.954 18.337 / }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\plot 8.333 20.003 9.525 19.050 / \putrule from 9.525 19.050 to 9.525 20.479 }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\plot 8.333 20.003 9.525 20.479 / \plot 9.525 20.479 10.954 19.765 / \putrule from 10.954 19.765 to 10.954 18.337 \plot 10.954 18.337 9.525 17.621 / \plot 9.525 17.621 8.333 18.098 / \plot 8.333 18.098 8.096 19.050 / \plot 8.096 19.050 8.333 20.003 / }% % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}4}% } [lB] at 9.644 19.408 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}3}% } [lB] at 7.739 19.884 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}2}% } [lB] at 7.499 18.931 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}1}% } [lB] at 7.739 17.979 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}2}% } [lB] at 9.406 16.787 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}1}% } [lB] at 11.311 18.216 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}2}% } [lB] at 11.309 19.647 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}1}% } [lB] at 9.406 20.955 \linethickness=0pt \putrectangle corners at 7.468 21.552 and 11.343 16.756 \endpicture} \end{center} \caption{\label{cap:4kriticky-graf}$4$-kritický graf} \end{figure} \end{rem*} \begin{rem} Každý graf $G$ s barevností $k=\chi(G)$ obsahuje $k$-kritický podgraf. \end{rem} \begin{proof} Stačí z $G$ postupně odebírat hrany takové, že neklesne barevnost. Jestliže už to nejde, máme $k$-kritický podgraf $G$. \end{proof} \begin{thm} Nechť $G=(V,E)$ je $k$-kritický graf. Potom $\delta(G)\geq k-1$. \end{thm} \begin{proof} Sporem: nechť $\left(\exists u\in V\right)\left(d_{G}(u)\leq k-2\right)$. Potom z $u$ vede méně hran, než kolik je potřeba barev na obarvení $G$, a to alespoň o $2$. Při každém vlastním obarvení není barva $u$ určena jednoznačně. Odeberme tedy vrchol $u$. Z $k$-kritičnosti $G$ lze zbytek grafu obarvit $k-1$ barvami. Jestliže nyní přidáme vrchol $u$ zpět, lze dát vrcholu $u$ alespoň $2$ různé barvy z dostupných $k$ barev. Proto nemusíme nutně vybrat novou ($k$-tou) barvu a $G$ se nám podaří obarvit $k-1$ barvami, což je spor. \end{proof} \begin{defn} Řekneme, že množina $S\subset V$ je \textbf{řezem} (angl. \emph{cut}) v grafu $G=(V,E)$, jestliže pro počty komponent platí $c(G)<c(G\backslash S)$. \end{defn} \begin{rem*} Když $S=\{ u\}$ je řez v souvislém grafu, pak graf musí vypadat jako na obrázku \ref{cap:jednoprvkovy-rez-grafem}.% \begin{figure} \begin{center} %Title: rez_grafem.fig %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 %%CreationDate: Thu Feb 12 19:29:04 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}\ellipticalarc axes ratio 0.356:0.356 360 degrees from 2.737 23.218 center at 2.381 23.218 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.356:0.356 360 degrees from 3.689 24.289 center at 3.334 24.289 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.356:0.356 360 degrees from 2.737 25.241 center at 2.381 25.241 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 2.381 24.289 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.356:0.356 360 degrees from 1.784 24.289 center at 1.429 24.289 }% % % Fig POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) \setdashes < 0.1080cm> {\color[rgb]{0,0,0}\plot 2.381 23.457 2.381 24.289 / }% % % Fig POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\plot 3.095 24.289 2.381 24.289 / }% % % Fig POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\plot 2.381 25.004 2.381 24.289 / }% % % Fig POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\plot 1.666 24.289 2.381 24.289 / }% % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{3}$}% } [lB] at 3.213 24.170 % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{2}$}% } [lB] at 2.142 25.121 % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{1}$}% } [lB] at 1.190 24.170 % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{4}$}% } [lB] at 2.142 23.097 % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$u$}% } [lB] at 2.024 23.933 \linethickness=0pt \putrectangle corners at 1.056 25.612 and 3.706 22.847 \endpicture} \end{center} \caption{\label{cap:jednoprvkovy-rez-grafem}Jednoprvkový řez grafem} \end{figure} \end{rem*} \begin{thm} \label{thm:rez-neni-klika}Řez $k$-kritického grafu není klika. \end{thm} \begin{proof} Sporem: nechť $G$ je $k$-kritický, $S$ je řez v $G$ a zároveň klika v $G$. Předpokládejme, že $S=\{ v_{1},...,v_{r}\}$, tj. $\# S=r$. Každé vlastní $k$-vrcholové obarvení musí přiřadit vrcholum z $S$ $r$ různých barev. Nechť $G\backslash S=G_{1}\cup G_{2}\cup...\cup G_{s}$. Potom vezmeme pro každé $i\in\hat{s}$ podgrafy $S\cup G_{i}$ (viz. obrázek \ref{cap:rez-neni-klika}) a obarvíme je $k-1$ barvami tak, aby barvy použité na vrcholech $S$ byly právě barvy $1,2,...,r$. (Víme, že existuje vlastní $(k-1)$-vrcholové obarvení těchto podgrafů, takže dodatečný požadavek lze zajistit jen vhodnou permutací barev.) Jestliže nyní všechny takto obarvené komponenty sjednotíme, získáme vlastní $(k-1)$-vrcholové obarvení grafu $G$, což je spor.% \begin{figure} \begin{center} %Title: rez_neni_klika.fig %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 %%CreationDate: Thu Feb 12 19:36:40 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}\ellipticalarc axes ratio 0.356:0.356 360 degrees from 2.737 22.979 center at 2.381 22.979 }% % % Fig POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) \setdashes < 0.1080cm> {\color[rgb]{0,0,0}\plot 2.381 23.218 2.381 24.052 / }% % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{4}$}% } [lB] at 2.142 22.860 % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) \setsolid {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.356:0.356 360 degrees from 3.926 24.289 center at 3.571 24.289 }% % % Fig POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) \setdashes < 0.1080cm> {\color[rgb]{0,0,0}\plot 3.334 24.289 2.618 24.289 / }% % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{3}$}% } [lB] at 3.452 24.170 % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) \setsolid {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.356:0.356 360 degrees from 2.737 25.480 center at 2.381 25.480 }% % % Fig POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) \setdashes < 0.1080cm> {\color[rgb]{0,0,0}\plot 2.381 25.241 2.381 24.528 / }% % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{2}$}% } [lB] at 2.142 25.360 % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) \setsolid {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.356:0.356 360 degrees from 1.545 24.289 center at 1.190 24.289 }% % % Fig POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) \setdashes < 0.1080cm> {\color[rgb]{0,0,0}\plot 1.429 24.289 2.142 24.289 / }% % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{1}$}% } [lB] at 0.950 24.170 % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) \setsolid {\color[rgb]{0,0,0}\ellipticalarc axes ratio 1.130:0.624 360 degrees from 2.915 24.289 center at 1.784 24.289 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.385:0.385 360 degrees from 2.766 24.289 center at 2.381 24.289 }% % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$S \cup G_{1}$}% } [lB] at 0.237 23.336 % % Fig TEXT object % \put{\SetFigFont{10}{12.0}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$S$}% } [lB] at 2.261 24.170 \linethickness=0pt \putrectangle corners at 0.205 25.851 and 3.943 22.608 \endpicture} \end{center} \caption{\label{cap:rez-neni-klika}K důkazu věty \ref{thm:rez-neni-klika}} \end{figure} \end{proof} \begin{rem*} V předchozím důkazu je skutečně důležité, aby $S$ byla klika. Pokud budeme stejně postupovat v případě obecné $S$, může se stát, že vlastní $(k-1)$-vrcholové obarvení podgrafů $S\cup G_{i}$ vynucuje, aby některé prvky $S$ byly obarveny stejnou barvou, přičemž pro různá $i\in\hat{s}$ se jedná o různé prvky. Nebude potom možné vhodně zpermutovat barvy, aby vrcholy z $S$ měly stejnou barvu nezávisle na $i$. \end{rem*} \subsection{Brooksova věta} \begin{lem} Nechť $G$ je $k$-kritický graf s řezem $S=\{ u,v\}$. Potom platí\[ d_{G}(u)+d_{G}(v)\geq3k-5.\] \end{lem} \begin{proof} Než dokážeme samotnou nerovnost, připravíme si tři pomocná tvrzení. Mějme při tom na paměti, že vrcholy $u,v$ nejsou podle předchozí věty \ref{thm:rez-neni-klika} spojeny hranou. \smallskip{} \textbf{Tvrzení 1.} \emph{Graf} $G\backslash\{ u,v\}$ \emph{(kde} $\{ u,v\}$ \emph{nemá smysl hrany, ale množiny vrcholů odebírané z} $V(G)$) \emph{se skládá z právě} $2$ \emph{komponent} $G_{1}=(V_{1},E_{1}),G_{2}=(V_{2},E_{2})$ \emph{takových, že} \begin{itemize} \item \emph{Každé vlastní} $(k-1)$\emph{-vrcholové obarvení (vlastního) indukovaného podgrafu} $A=G[V_{1}\cup\{ u,v\}]$ \emph{přiřazuje vrcholům} $u,v$ \emph{stejnou barvu. (Jinými slovy: barvíme-li} $A$ \emph{pomocí} $k-1$ \emph{barev, musíme dát} $u$ \emph{a} $v$ \emph{stejnou barvu)} \item \emph{Každé vlastní} $(k-1)$\emph{-vrcholové obarvení (vlastního) indukovaného podgrafu} $B=G[V_{2}\cup\{ u,v\}]$ \emph{přiřazuje vrcholům} $u,v$ \emph{různou barvu.} \end{itemize} \hfill{} \begin{center} %Title: brooks_lemma1.fig %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 %%CreationDate: Thu Feb 12 19:36:16 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.191}}} at 10.478 19.215 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.191}}} at 10.478 19.840 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\ellipticalarc axes ratio 3.095:2.024 360 degrees from 13.572 19.526 center at 10.478 19.526 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\ellipticalarc axes ratio 1.547:1.556 360 degrees from 12.857 19.526 center at 11.309 19.526 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\ellipticalarc axes ratio 1.547:1.556 360 degrees from 11.191 19.526 center at 9.644 19.526 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.595:0.931 360 degrees from 9.525 19.526 center at 8.930 19.526 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.595:0.931 360 degrees from 12.620 19.526 center at 12.025 19.526 }% % % Fig POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) \setdashes < 0.1080cm> {\color[rgb]{0,0,0}\plot 10.478 19.215 11.667 19.215 / }% % % Fig POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\plot 10.478 19.215 9.286 19.215 / }% % % Fig POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\plot 10.478 19.840 11.667 19.840 / }% % % Fig POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\plot 10.478 19.840 9.286 19.840 / }% % % Fig TEXT object % \put{\SetFigFont{14}{16.8}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G$}% } [lB] at 10.240 17.659 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$B$}% } [lB] at 11.311 18.282 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$A$}% } [lB] at 9.404 18.282 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{2}$}% } [lB] at 11.906 19.450 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{1}$}% } [lB] at 8.572 19.450 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v$}% } [lB] at 10.357 18.707 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$u$}% } [lB] at 10.357 20.151 \linethickness=0pt \putrectangle corners at 7.366 21.565 and 13.589 17.471 \endpicture} \end{center} \hfill{} \emph{Důkaz tvrzení 1:} Zpočátku nevíme, zda $G\backslash\{ u,v\}$ obsahuje \emph{jen} dvě komponenty. Lze však tvrdit, že $G\backslash\{ u,v\}$ musí obsahovat alespoň jednu komponentu s vlastností komponenty $G_{1}$. Kdyby to tak nebylo, mohli bychom každý podgraf grafu $G$ indukovaný vrcholy jedné z komponent a vrcholy $u,v$ obarvit $k-1$ barvami tak, že $u$ a $v$ by měly různé barvy. Potom bychom barvy zpermutovali tak, aby $u,v$ měly vždy barvy $1,2$. Takto obarvené podgrafy bychom sjednotili a získali tak celý graf $G$ obarvený $k-1$ barvami, což je spor. Ze stejného důvodu obsahuje $G\backslash\{ u,v\}$ alespoň jednu komponentu s vlastností $G_{2}$. Nyní si tyto komponenty označíme přímo jako $G_{1}$ a $G_{2}$. Ukážeme, že žádné jiné komponenty už v $G\backslash\{ u,v\}$ neexistují: Indukovaný podgraf $A\cup B=G[V_{1}\cup V_{2}\cup\{ u,v\}]$ podle vlastností komponent $G_{1}$ a $G_{2}$ nejde (vlastním obarvením) obarvit $k-1$ barvami, protože vrcholy $u,v$ nemohou mít současně podle $G_{1}$ stejnou a podle $G_{2}$ různou barvu. Proto $\chi(A\cup B)=k$. Protože $G$ je $k$-kritický, musí platit $G=A\cup B$. \smallskip{} \textbf{Tvrzení 2.} \emph{Podgraf} $C=A\cup\{\{ u,v\}\}$\emph{, který vznikne přidáním hrany} $\{ u,v\}$ \emph{do} $A$\emph{, je již} $k$\emph{-kritický.} \hfill{} \begin{center} %Title: brooks_lemma2.fig %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 %%CreationDate: Thu Feb 12 19:23: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.191}}} at 10.478 19.215 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.191}}} at 10.478 19.840 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\ellipticalarc axes ratio 1.547:1.556 360 degrees from 11.191 19.526 center at 9.644 19.526 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\ellipticalarc axes ratio 0.595:0.931 360 degrees from 9.525 19.526 center at 8.930 19.526 }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\putrule from 10.478 19.884 to 10.478 19.171 }% % % Fig POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) \setdashes < 0.1080cm> {\color[rgb]{0,0,0}\plot 10.478 19.215 9.286 19.215 / }% % % Fig POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\plot 10.478 19.840 9.286 19.840 / }% % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$C$}% } [lB] at 9.404 18.282 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{1}$}% } [lB] at 8.572 19.450 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$v$}% } [lB] at 10.357 18.707 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$u$}% } [lB] at 10.357 20.151 \linethickness=0pt \putrectangle corners at 8.079 21.099 and 11.208 17.954 \endpicture} \end{center} \hfill{} \emph{Důkaz tvrzení 2:} Zřejmě platí $\chi(C)=k$, protože $A$ lze obarvit $k-1$ barvami jen tak, že $u,v$ mají stejnou barvu. Když je tedy spojíme hranou, tak už to nejde. Ubereme-li z $G$ libovolnou hranu, lze jej obarvit $k-1$ barvami. Pokud navíc tato hrana leží v podgrafu $A$, zůstává ve výsledném grafu celý podgraf $B$, takže v uvedeném vlastním obarvení musí mít $u,v$ různou barvu. Proto nezáleží na tom, zda je navíc spojíme hranou. Tím jsme dokázali, že po ubrání čehokoliv z $C$ vznikne graf s barevností $k-1$, takže $C$ je $k$-kritický. \smallskip{} \textbf{Tvrzení 3.} \emph{Označme jako} $D$ \emph{graf, který vznikne z grafu} $B$ \emph{sloučením vrcholů} $u,v$ \emph{do nového vrcholu} $w$. \emph{Potom} $D$ \emph{je} $k$\emph{-kritický.} \hfill{} \begin{center} %Title: brooks_lemma3.fig %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 %%CreationDate: Thu Feb 12 19:17: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}\ellipticalarc axes ratio 0.595:0.931 360 degrees from 3.332 25.123 center at 2.737 25.123 }% % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\ellipticalarc axes ratio 1.547:1.556 360 degrees from 3.569 25.123 center at 2.021 25.123 }% % % Fig POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) \setdashes < 0.1080cm> {\color[rgb]{0,0,0}\plot 1.190 25.123 2.379 25.436 / }% % % Fig POLYLINE object % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\plot 1.190 25.123 2.379 24.812 / }% % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$D$}% } [lB] at 2.024 23.878 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$w$}% } [lB] at 1.010 25.449 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}$G_{2}$}% } [lB] at 2.618 25.047 % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) \setsolid {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.191}}} at 1.190 25.123 }% \linethickness=0pt \putrectangle corners at 0.457 26.695 and 3.586 23.550 \endpicture} \end{center} \hfill{} \emph{Důkaz tvrzení 3:} Analogicky jako tvrzení 2. $\chi(D)=k$, neboť $B$ lze obarvit $k-1$ barvami, jen když $u,v$ mají různou barvu. Jejich spojením do $w$ však vynucujeme stejnou. Ubereme-li z $G$ libovolnou hranu, lze jej obarvit $k-1$ barvami. Pokud navíc tato hrana leží v podgrafu $B$, zůstává ve výsledném grafu celý podgraf $A$, takže v uvedeném vlastním obarvení musí mít $u,v$ stejnou barvu. Proto (z hlediska obarvení) nezáleží na tom, zda je navíc sloučíme do $w$. Tím jsme dokázali, že po ubrání čehokoliv z $D$ vznikne graf s barevností $k-1$, takže $D$ je $k$-kritický. \smallskip{} Nyní konečně můžeme dokázat uvedenou nerovnost. Zřejmě platí následující vztahy:\begin{eqnarray*} d_{G}(u) & = & d_{A}(u)+d_{B}(u),\\ d_{G}(v) & = & d_{A}(v)+d_{B}(v),\\ d_{C}(u) & = & d_{A}(u)+1,\\ d_{C}(v) & = & d_{A}(v)+1,\\ d_{D}(w) & = & d_{B}(u)+d_{B}(v).\end{eqnarray*} Protože v $k$-kritickém grafu platí $\delta\geq k-1$, dostáváme\[ d_{G}(u)+d_{G}(v)=d_{A}(u)+d_{B}(u)+d_{A}(v)+d_{B}(v)=\] \[ =\underbrace{d_{C}(u)}_{\geq k-1}+\underbrace{d_{C}(v)}_{\geq k-1}-2+\underbrace{d_{D}(w)}_{\geq k-1}\geq3k-5.\] \end{proof} \begin{thm} \textbf{\emph{(Brooks)}} Nechť $G$ je souvislý graf , a přitom $G$ není ani klika ani kružnice liché délky. Potom $\chi(G)\leq\Delta(G)$. \end{thm} \begin{rem*} Velmi snadno jsme již dokázali, že pro každý graf platí $\chi(G)\leq\Delta(G)+1$. Nyní bude důkaz obtížnější. \end{rem*} \begin{proof} Nejprve ukážeme, že BÚNO lze důkaz provést pouze pro $k$-kritické grafy. Mějme tedy souvislý graf, ani kliku ani lichou kružnici, který navíc \emph{není} $k$-kritický. Potom najdeme jeho vlastní $k$-kritický podgraf $H$. Platí tedy $\chi(H)=\chi(G)=k$ a zřejmě též $\Delta(H)\leq\Delta(G)$. Mohou nastat následující možnosti: \begin{enumerate} \item $H$ není klika ani lichá kružnice. Potom použijeme naše tvrzení dokázané pro $k$-kritické grafy: $\chi(H)\leq\Delta(H)$. Z toho plyne\[ \chi(G)=\chi(H)\leq\Delta(H)=\Delta(G).\] \item $H$ je klika. Naše tvrzení použít nemůžeme, zato je nyní zřejmě $\Delta(H)<\Delta(G)$, protože $H$ je vlastním podgrafem souvislého grafu $G$. Protože pro libovolný graf $\tilde{G}$ platí $\chi(\tilde{G})\leq\Delta(\tilde{G})+1$, tak\[ \chi(G)=\chi(H)\leq\Delta(H)+1\leq\Delta(G).\] \item $H$ je lichá kružnice. Zde je zdůvodnění obdobné tomu v předchozím bodě: Každý vrchol grafu $H$ má stupeň $2$ a tak $\Delta(H)=2$. Protože ale $G$ je souvislý a $H$ je vlastním podgrafem $G$, tak v $G$ musí být na nějaký vrchol z kružnice $H$ napojena alespoň jedna další hrana. To opět znamená $\Delta(H)<\Delta(G)$, zbytek je stejný. \end{enumerate} Nyní dokážeme samotné tvrzení pouze pro $k$-kritické grafy, které ovšem budeme označovat opět jako ,,$G${}``. Platí tedy $k=\chi(G)$. Podle poznámky \ref{rem:123kriticke-grafy} je zřejmé, že $k\geq4$, protože jinak by nebyly splněny předpoklady věty. Mohou nastat dvě možnosti: \bigskip{} \textbf{a)} Nechť v $G$ existuje řez $S=\{ u,v\}$. Potom podle předchozí věty platí\[ 2\Delta(G)\geq d_{G}(u)+d_{G}(v)\geq3k-5=2k-1+\underbrace{k-4}_{\geq0}\geq2k-1.\] Na levé straně nerovnosti však máme sudé číslo a na pravé straně je liché číslo. Proto samozřejmě musí platit i $2\Delta(G)\geq2k$, neboli\[ \Delta(G)\geq k=\chi(G).\] \bigskip{} \textbf{b)} Nechť v $G$ neexistuje dvouprvkový řez. To znamená, že po odebrání libovolných dvou vrcholů $u,v$ zůstává graf $G\backslash\{ u,v\}$ souvislý. Z předpokladu ,,$G$ není klika{}`` najdeme v $G$ vrcholy $u,v$, které nejsou spojeny hranou, takže jejich vzdálenost $d(u,v)\geq2$. Tím pádem najdeme $u,v$ i tak, že $d(u,v)=2$. Označme jako $w$ vrchol, přes který jsou spojeny. \hfill{} \begin{center} %Title: brooks_uvw.fig %%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7 %%CreationDate: Thu Feb 12 18:00:48 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 7.620 20.955 }% % % Fig POLYLINE object % \linethickness=1pt \setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}}) {\color[rgb]{0,0,0}\plot 7.620 20.955 9.049 20.479 / \plot 9.049 20.479 7.620 20.003 / }% % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}w}% } [lB] at 9.404 20.360 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}v}% } [lB] at 7.023 19.884 % % Fig TEXT object % \put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}u}% } [lB] at 7.023 20.836 % % Fig ELLIPSE % \linethickness= 0.500pt \setplotsymbol ({\thinlinefont .}) {\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.237}}} at 9.049 20.479 }% \linethickness=0pt \putrectangle corners at 6.991 21.433 and 9.436 19.852 \endpicture} \end{center} \hfill{} Nyní očíslujeme vrcholy grafu $G$ speciálním způsobem. \begin{itemize} \item Označíme $v_{1}=u,v_{2}=v,v_{n}=w$. \item $v_{3},v_{4},v_{5},...,v_{n}=w$ budou vrcholy grafu $G\backslash\{ u,v\}$ uspořádané tak, že\[ \left(\forall i\in\{3,4,...,n-1\}\right)\left(\exists j>i\right)\left(\{ v_{i},v_{j}\}\in E\right),\] neboli z každého vrcholu $v_{3},v_{4},v_{5},...,v_{n-1}$ vede v grafu $G\backslash\{ u,v\}$ hrana do nějakého vrcholu, který je v uspořádání až za ním. Takové uspořádání vznikne například tak, že vrcholy $v_{3},v_{4},v_{5},...,v_{n}$ seřadíme sestupně podle jejich vzdálenosti od vrcholu $w$ v grafu $G\backslash\{ u,v\}$, tj. budou splňovat\[ \left(\forall i,j\in\{3,4,...,n\}\right)\left(i<j\Rightarrow d_{G\backslash\{ u,v\}}(v_{i},w\}\geq d_{G\backslash\{ u,v\}}(v_{j},w\}\right).\] V tom případě zřejmě $v_{n}=w$. \end{itemize} Takto uspořádané vrcholy $v_{1},...,v_{n}$ grafu $G$ už lze obarvit nejvýše $\Delta(G)$ barvami, a to takto: \begin{itemize} \item Vrcholy $v_{1}=u,v_{2}=v$ dostanou barvu $1$, což je možné, neboť spolu nesousedí. \item Vrcholy $v_{3},v_{4},...,v_{n-1}$ obarvujeme postupně první barvou, kterou je možné použít. Protože z každého z nich vede hrana do ještě neobarvených vrcholů, má každý z nich ve chvíli, když na něj přijde řada, nejvýše $\Delta(G)-1$ již obarvených sousedů, a tak existuje barva $b\in\{1,2,...,\Delta(G)\}$, kterou jej lze obarvit. \item Vrchol $v_{n}=w$ sousedí s vrcholy $u,v$, které mají oba barvu $1$, a dále s nejvýše $\Delta(G)-2$ dalšími vrcholy, které mají nejvýše $\Delta(G)-2$ různých barev. Celkem tedy sousedí s nejvýše $\Delta(G)$ vrcholy, které mají nejvýše $\Delta(G)-1$ různých barev, a tak jej lze také obarvit. \end{itemize} \end{proof}