Aktuální verze z 15. 1. 2012, 12:50

Zdrojový kód

%\wikiskriptum{01ZTGA}
 
\section{Bipartitní grafy}
 
\begin{defn}
Řekneme, že graf $G=(V,E)$ je \textbf{bipartitní} (angl. \emph{bipartite}),
existuje-li rozklad množiny $V$ na dvě disjunktní neprázdné množiny
$V_{1},V_{2}$ takový, že $E\cap\binom{V_{1}}{2}=\emptyset$, $E\cap\binom{V_{2}}{2}=\emptyset$,
tj. takový, že mezi žádnými dvěma vrcholy z $V_{1}$ ani mezi žádnými
dvěma vrcholy z $V_{2}$ nevede hrana.
\end{defn}
\begin{rem}
Jestliže je $G$ bipartitní, lze očíslovat vrcholy tak, že prvních
$k$ vrcholů leží ve $V_{1}$ a zbylých $n-k$ vrcholů ve $V_{2}$.
Adjacenční matice má potom tvar\[
\vec{A}_{G}=\left(\begin{array}{cc}
\vec{0} & \vec{B}\\
\vec{B}^{\T} & \vec{0}\end{array}\right).\]
Naopak: $G$ je bipartitní, existuje-li permutace vrcholů (a tedy
zároveň řádků i sloupců matice $\vec{A}_{G}$) taková, že $\vec{A}_{G}$
má uvedený tvar.
\end{rem}
\begin{defn}
Bipartitní graf $G=(V_{1}\cup V_{2},E)$ se nazývá \textbf{úplný},
jestliže $\left(\forall u\in V_{1}\right)\left(\forall v\in V_{2}\right)\left(\{ u,v\}\in E\right)$.
\end{defn}
\begin{thm}
Buď $G=(V,E)$ graf, $\# V\geq2$. Potom $G$ je bipartitní právě
tehdy, když neobsahuje kružnici liché délky.
\end{thm}
\begin{proof}
$\boxed{{\Rightarrow:}}$
 
Libovolná kružnice prochází střídavě vrcholy z $V_{1}$ a $V_{2}$.
Zvolíme-li nějaký vrchol za počáteční a půjdeme po kružnici, nakonec
se do tohoto vrcholu vrátíme. Jdeme tedy několikrát z $V_{1}$ do
$V_{2}$ a zpět, takže kružnice nemůže mít lichou délku.
 
$\boxed{{\Leftarrow:}}$
 
Nejprve předpokládejme, že $G$ je souvislý. Nechť tedy v $G$ neexistuje
kružnice liché délky. Zvolme libovolně $u\in V$ a definujme nejkrat\v{s}í cesta z u do v má sudou délku
\[
V_{1}=\left\{ \left.v\in V\right|\textrm{ nejkrat\v{s}í cesta z }u\textrm{ do }v\textrm{ má sudou délku}\right\} ,\]
\[
V_{2}=V\backslash V_{1}.\]
Protože $G$ je souvislý, tak vrcholy z $V_{2}$ mají nejkratší cestu
do $u$ liché délky.
 
Platí zřejmě $u\in V_{1},V_{1}\cap V_{2}=\emptyset$ a navíc z $u$
určitě vede nějaká hrana, třeba do vrcholu $z$, což znamená, že $z\in V_{2}$
(nejkratší cesta z $u$ do $z$ je po jediné hraně, tj. má délku $1$,
a to je liché číslo). $V_{1}$i $V_{2}$ jsou tedy neprázdné. Ukážeme
sporem, že ve $V_{1}$ nevede hrana:
 
Nechť $\left(\exists x,y\in V_{1}\right)\left(\{ x,y\}\in E\right)$.
Buď $P_{x}$ nejkratší cesta z $u$ do $x$, podobně $P_{y}$ nejkratší
cesta z $u$ do $y$. $P_{x}$ i $P_{y}$ jsou sudé délky. Označmě
$z$ nejbližší bod od bodů $x,y$ na cestách $P_{x}$ a $P_{y}$,
který je pro obě cesty stejný (v krajním případě může být tímto bodem
i $u$), viz obrázek \ref{cap:bipart_dukaz}. Potom úsek cesty $P_{x}$
mezi $z$ a $u$ je stejně dlouhý jako tentýž úsek po cestě $P_{y}$.
Kdyby tomu tak nebylo, mohli bychom ten kratší z nich (nechť je to
třeba úsek $P_{x}$) použít pro vytvoření kratší cesty z $y$ do $u$,
což je spor s volbou $P_{y}$ jako nejkratší cesty.%
\begin{figure}
\begin{center}
%Title: bipart_dukaz.fig
%%Created by: ..\UTILS\FIG2DEV.EXE Version 3.2 Patchlevel 5-alpha7
%%CreationDate: Thu Feb 12 22:14: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.339}}} at  1.090 25.991
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.339}}} at  1.090 23.271
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.339}}} at  4.489 24.630
}%
%
% Fig ELLIPSE
%
\linethickness= 0.500pt
\setplotsymbol ({\thinlinefont .})
{\color[rgb]{0,0,0}\put{\makebox(0,0)[l]{\circle*{ 0.339}}} at  6.530 24.630
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  1.090 25.991  1.092 25.984 /
\plot  1.092 25.984  1.099 25.974 /
\plot  1.099 25.974  1.107 25.950 /
\plot  1.107 25.950  1.124 25.916 /
\plot  1.124 25.916  1.145 25.868 /
\plot  1.145 25.868  1.175 25.802 /
\plot  1.175 25.802  1.211 25.724 /
\plot  1.211 25.724  1.251 25.633 /
\plot  1.251 25.633  1.300 25.527 /
\plot  1.300 25.527  1.353 25.411 /
\plot  1.353 25.411  1.410 25.288 /
\plot  1.410 25.288  1.469 25.159 /
\plot  1.469 25.159  1.530 25.025 /
\plot  1.530 25.025  1.594 24.894 /
\plot  1.594 24.894  1.657 24.763 /
\plot  1.657 24.763  1.719 24.634 /
\plot  1.719 24.634  1.778 24.511 /
\plot  1.778 24.511  1.835 24.397 /
\plot  1.835 24.397  1.890 24.287 /
\plot  1.890 24.287  1.943 24.185 /
\plot  1.943 24.185  1.992 24.092 /
\plot  1.992 24.092  2.038 24.007 /
\plot  2.038 24.007  2.083 23.931 /
\plot  2.083 23.931  2.123 23.863 /
\plot  2.123 23.863  2.161 23.802 /
\plot  2.161 23.802  2.197 23.751 /
\plot  2.197 23.751  2.231 23.705 /
\plot  2.231 23.705  2.263 23.669 /
\plot  2.263 23.669  2.292 23.637 /
\plot  2.292 23.637  2.320 23.614 /
\plot  2.320 23.614  2.345 23.597 /
\plot  2.345 23.597  2.371 23.586 /
\plot  2.371 23.586  2.394 23.582 /
\plot  2.394 23.582  2.424 23.584 /
\plot  2.424 23.584  2.451 23.592 /
\plot  2.451 23.592  2.477 23.611 /
\plot  2.477 23.611  2.502 23.639 /
\plot  2.502 23.639  2.525 23.673 /
\plot  2.525 23.673  2.548 23.713 /
\plot  2.548 23.713  2.572 23.762 /
\plot  2.572 23.762  2.595 23.817 /
\plot  2.595 23.817  2.616 23.876 /
\plot  2.616 23.876  2.637 23.942 /
\plot  2.637 23.942  2.656 24.009 /
\plot  2.656 24.009  2.678 24.081 /
\plot  2.678 24.081  2.697 24.155 /
\plot  2.697 24.155  2.718 24.229 /
\plot  2.718 24.229  2.737 24.306 /
\plot  2.737 24.306  2.756 24.380 /
\plot  2.756 24.380  2.775 24.452 /
\plot  2.775 24.452  2.794 24.522 /
\plot  2.794 24.522  2.813 24.589 /
\plot  2.813 24.589  2.832 24.653 /
\plot  2.832 24.653  2.851 24.710 /
\plot  2.851 24.710  2.872 24.763 /
\plot  2.872 24.763  2.893 24.809 /
\plot  2.893 24.809  2.915 24.852 /
\plot  2.915 24.852  2.936 24.886 /
\plot  2.936 24.886  2.959 24.913 /
\plot  2.959 24.913  2.989 24.936 /
\plot  2.989 24.936  3.020 24.951 /
\plot  3.020 24.951  3.054 24.955 /
\plot  3.054 24.955  3.090 24.953 /
\plot  3.090 24.953  3.128 24.941 /
\plot  3.128 24.941  3.167 24.924 /
\plot  3.167 24.924  3.209 24.898 /
\plot  3.209 24.898  3.253 24.867 /
\plot  3.253 24.867  3.298 24.829 /
\plot  3.298 24.829  3.344 24.786 /
\plot  3.344 24.786  3.393 24.742 /
\plot  3.393 24.742  3.440 24.693 /
\plot  3.440 24.693  3.488 24.642 /
\plot  3.488 24.642  3.535 24.591 /
\plot  3.535 24.591  3.581 24.541 /
\plot  3.581 24.541  3.626 24.492 /
\plot  3.626 24.492  3.670 24.443 /
\plot  3.670 24.443  3.713 24.399 /
\plot  3.713 24.399  3.753 24.359 /
\plot  3.753 24.359  3.793 24.323 /
\plot  3.793 24.323  3.829 24.289 /
\plot  3.829 24.289  3.867 24.261 /
\plot  3.867 24.261  3.901 24.240 /
\plot  3.901 24.240  3.935 24.223 /
\plot  3.935 24.223  3.967 24.213 /
\plot  3.967 24.213  4.000 24.208 /
\plot  4.000 24.208  4.032 24.210 /
\plot  4.032 24.210  4.066 24.217 /
\plot  4.066 24.217  4.100 24.232 /
\plot  4.100 24.232  4.136 24.251 /
\plot  4.136 24.251  4.172 24.276 /
\plot  4.172 24.276  4.210 24.308 /
\plot  4.210 24.308  4.248 24.342 /
\plot  4.248 24.342  4.286 24.382 /
\plot  4.286 24.382  4.324 24.424 /
\plot  4.324 24.424  4.362 24.467 /
\plot  4.362 24.467  4.396 24.507 /
\plot  4.396 24.507  4.426 24.545 /
\plot  4.426 24.545  4.449 24.575 /
\plot  4.449 24.575  4.468 24.600 /
\plot  4.468 24.600  4.479 24.617 /
\plot  4.479 24.617  4.487 24.625 /
\plot  4.487 24.625  4.489 24.630 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  4.489 24.630  4.494 24.634 /
\plot  4.494 24.634  4.502 24.646 /
\plot  4.502 24.646  4.517 24.666 /
\plot  4.517 24.666  4.542 24.695 /
\plot  4.542 24.695  4.572 24.733 /
\plot  4.572 24.733  4.612 24.780 /
\plot  4.612 24.780  4.655 24.831 /
\plot  4.655 24.831  4.703 24.884 /
\plot  4.703 24.884  4.752 24.936 /
\plot  4.752 24.936  4.801 24.987 /
\plot  4.801 24.987  4.849 25.032 /
\plot  4.849 25.032  4.896 25.072 /
\plot  4.896 25.072  4.942 25.106 /
\plot  4.942 25.106  4.985 25.133 /
\plot  4.985 25.133  5.027 25.154 /
\plot  5.027 25.154  5.065 25.169 /
\plot  5.065 25.169  5.103 25.176 /
\putrule from  5.103 25.176 to  5.141 25.176
\plot  5.141 25.176  5.179 25.169 /
\plot  5.179 25.169  5.218 25.159 /
\plot  5.218 25.159  5.256 25.140 /
\plot  5.256 25.140  5.292 25.118 /
\plot  5.292 25.118  5.330 25.091 /
\plot  5.330 25.091  5.368 25.061 /
\plot  5.368 25.061  5.406 25.025 /
\plot  5.406 25.025  5.448 24.985 /
\plot  5.448 24.985  5.489 24.943 /
\plot  5.489 24.943  5.531 24.896 /
\plot  5.531 24.896  5.575 24.848 /
\plot  5.575 24.848  5.620 24.795 /
\plot  5.620 24.795  5.664 24.742 /
\plot  5.664 24.742  5.709 24.685 /
\plot  5.709 24.685  5.753 24.630 /
\plot  5.753 24.630  5.798 24.575 /
\plot  5.798 24.575  5.842 24.517 /
\plot  5.842 24.517  5.884 24.464 /
\plot  5.884 24.464  5.925 24.412 /
\plot  5.925 24.412  5.965 24.363 /
\plot  5.965 24.363  6.003 24.316 /
\plot  6.003 24.316  6.039 24.274 /
\plot  6.039 24.274  6.073 24.234 /
\plot  6.073 24.234  6.104 24.198 /
\plot  6.104 24.198  6.136 24.168 /
\plot  6.136 24.168  6.164 24.141 /
\plot  6.164 24.141  6.191 24.119 /
\plot  6.191 24.119  6.221 24.100 /
\plot  6.221 24.100  6.248 24.088 /
\plot  6.248 24.088  6.274 24.081 /
\plot  6.274 24.081  6.299 24.086 /
\plot  6.299 24.086  6.320 24.096 /
\plot  6.320 24.096  6.344 24.115 /
\plot  6.344 24.115  6.365 24.143 /
\plot  6.365 24.143  6.386 24.179 /
\plot  6.386 24.179  6.407 24.223 /
\plot  6.407 24.223  6.426 24.272 /
\plot  6.426 24.272  6.447 24.329 /
\plot  6.447 24.329  6.464 24.386 /
\plot  6.464 24.386  6.483 24.443 /
\plot  6.483 24.443  6.498 24.498 /
\plot  6.498 24.498  6.509 24.545 /
\plot  6.509 24.545  6.519 24.583 /
\plot  6.519 24.583  6.526 24.608 /
\plot  6.526 24.608  6.528 24.623 /
\plot  6.528 24.623  6.530 24.630 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
\setdots < 0.3048cm>
{\color[rgb]{0,0,0}\plot  4.489 24.630  4.494 24.623 /
\plot  4.494 24.623  4.502 24.613 /
\plot  4.502 24.613  4.519 24.591 /
\plot  4.519 24.591  4.542 24.560 /
\plot  4.542 24.560  4.574 24.519 /
\plot  4.574 24.519  4.612 24.471 /
\plot  4.612 24.471  4.657 24.416 /
\plot  4.657 24.416  4.705 24.359 /
\plot  4.705 24.359  4.756 24.299 /
\plot  4.756 24.299  4.807 24.244 /
\plot  4.807 24.244  4.856 24.191 /
\plot  4.856 24.191  4.904 24.143 /
\plot  4.904 24.143  4.951 24.098 /
\plot  4.951 24.098  4.995 24.062 /
\plot  4.995 24.062  5.038 24.031 /
\plot  5.038 24.031  5.080 24.005 /
\plot  5.080 24.005  5.120 23.984 /
\plot  5.120 23.984  5.160 23.969 /
\plot  5.160 23.969  5.201 23.956 /
\plot  5.201 23.956  5.243 23.952 /
\plot  5.243 23.952  5.283 23.950 /
\plot  5.283 23.950  5.323 23.950 /
\plot  5.323 23.950  5.364 23.956 /
\plot  5.364 23.956  5.408 23.965 /
\plot  5.408 23.965  5.453 23.978 /
\plot  5.453 23.978  5.501 23.995 /
\plot  5.501 23.995  5.552 24.016 /
\plot  5.552 24.016  5.609 24.043 /
\plot  5.609 24.043  5.668 24.073 /
\plot  5.668 24.073  5.734 24.109 /
\plot  5.734 24.109  5.804 24.149 /
\plot  5.804 24.149  5.878 24.196 /
\plot  5.878 24.196  5.956 24.244 /
\plot  5.956 24.244  6.039 24.295 /
\plot  6.039 24.295  6.119 24.348 /
\plot  6.119 24.348  6.200 24.401 /
\plot  6.200 24.401  6.276 24.454 /
\plot  6.276 24.454  6.344 24.500 /
\plot  6.344 24.500  6.403 24.541 /
\plot  6.403 24.541  6.452 24.575 /
\plot  6.452 24.575  6.488 24.600 /
\plot  6.488 24.600  6.511 24.617 /
\plot  6.511 24.617  6.524 24.625 /
\plot  6.524 24.625  6.530 24.630 /
}%
%
% Fig POLYLINE object
%
\linethickness=1pt
\setplotsymbol ({\makebox(0,0)[l]{\tencirc\symbol{'160}}})
{\color[rgb]{0,0,0}\plot  1.090 23.271  1.092 23.275 /
\plot  1.092 23.275  1.096 23.288 /
\plot  1.096 23.288  1.107 23.309 /
\plot  1.107 23.309  1.122 23.343 /
\plot  1.122 23.343  1.143 23.389 /
\plot  1.143 23.389  1.168 23.448 /
\plot  1.168 23.448  1.202 23.523 /
\plot  1.202 23.523  1.240 23.609 /
\plot  1.240 23.609  1.285 23.705 /
\plot  1.285 23.705  1.334 23.810 /
\plot  1.334 23.810  1.384 23.920 /
\plot  1.384 23.920  1.439 24.035 /
\plot  1.439 24.035  1.494 24.149 /
\plot  1.494 24.149  1.549 24.263 /
\plot  1.549 24.263  1.604 24.373 /
\plot  1.604 24.373  1.657 24.479 /
\plot  1.657 24.479  1.710 24.581 /
\plot  1.710 24.581  1.759 24.674 /
\plot  1.759 24.674  1.808 24.761 /
\plot  1.808 24.761  1.854 24.839 /
\plot  1.854 24.839  1.897 24.911 /
\plot  1.897 24.911  1.939 24.977 /
\plot  1.939 24.977  1.979 25.034 /
\plot  1.979 25.034  2.017 25.083 /
\plot  2.017 25.083  2.053 25.127 /
\plot  2.053 25.127  2.087 25.163 /
\plot  2.087 25.163  2.123 25.193 /
\plot  2.123 25.193  2.155 25.216 /
\plot  2.155 25.216  2.189 25.233 /
\plot  2.189 25.233  2.220 25.245 /
\plot  2.220 25.245  2.252 25.254 /
\plot  2.252 25.254  2.294 25.256 /
\plot  2.294 25.256  2.335 25.250 /
\plot  2.335 25.250  2.379 25.237 /
\plot  2.379 25.237  2.421 25.216 /
\plot  2.421 25.216  2.464 25.188 /
\plot  2.464 25.188  2.508 25.154 /
\plot  2.508 25.154  2.553 25.116 /
\plot  2.553 25.116  2.597 25.072 /
\plot  2.597 25.072  2.642 25.021 /
\plot  2.642 25.021  2.688 24.968 /
\plot  2.688 24.968  2.733 24.911 /
\plot  2.733 24.911  2.777 24.854 /
\plot  2.777 24.854  2.822 24.793 /
\plot  2.822 24.793  2.866 24.733 /
\plot  2.866 24.733  2.908 24.674 /
\plot  2.908 24.674  2.951 24.615 /
\plot  2.951 24.615  2.993 24.560 /
\plot  2.993 24.560  3.031 24.507 /
\plot  3.031 24.507  3.069 24.458 /
\plot  3.069 24.458  3.107 24.414 /
\plot  3.107 24.414  3.143 24.376 /
\plot  3.143 24.376  3.177 24.340 /
\plot  3.177 24.340  3.211 24.312 /
\plot  3.211 24.312  3.243 24.289 /
\plot  3.243 24.289  3.279 24.272 /
\plot  3.279 24.272  3.313 24.261 /
\plot  3.313 24.261  3.349 24.257 /
\plot  3.349 24.257  3.382 24.259 /
\plot  3.382 24.259  3.418 24.268 /
\plot  3.418 24.268  3.452 24.282 /
\plot  3.452 24.282  3.488 24.301 /
\plot  3.488 24.301  3.522 24.327 /
\plot  3.522 24.327  3.558 24.354 /
\plot  3.558 24.354  3.594 24.386 /
\plot  3.594 24.386  3.628 24.422 /
\plot  3.628 24.422  3.662 24.458 /
\plot  3.662 24.458  3.696 24.498 /
\plot  3.696 24.498  3.727 24.536 /
\plot  3.727 24.536  3.759 24.577 /
\plot  3.759 24.577  3.789 24.615 /
\plot  3.789 24.615  3.818 24.653 /
\plot  3.818 24.653  3.846 24.687 /
\plot  3.846 24.687  3.873 24.721 /
\plot  3.873 24.721  3.901 24.750 /
\plot  3.901 24.750  3.926 24.776 /
\plot  3.926 24.776  3.952 24.799 /
\plot  3.952 24.799  3.981 24.822 /
\plot  3.981 24.822  4.011 24.839 /
\plot  4.011 24.839  4.041 24.850 /
\plot  4.041 24.850  4.072 24.856 /
\plot  4.072 24.856  4.106 24.854 /
\plot  4.106 24.854  4.142 24.848 /
\plot  4.142 24.848  4.178 24.835 /
\plot  4.178 24.835  4.221 24.816 /
\plot  4.221 24.816  4.263 24.793 /
\plot  4.263 24.793  4.305 24.767 /
\plot  4.305 24.767  4.350 24.737 /
\plot  4.350 24.737  4.390 24.708 /
\plot  4.390 24.708  4.426 24.680 /
\plot  4.426 24.680  4.453 24.659 /
\plot  4.453 24.659  4.473 24.644 /
\plot  4.473 24.644  4.485 24.634 /
\plot  4.485 24.634  4.489 24.630 /
}%
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}x}%
} [lB] at  0.239 25.819
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}y}%
} [lB] at  0.239 23.099
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}z}%
} [lB] at  4.489 25.309
%
% Fig TEXT object
%
\put{\SetFigFont{12}{14.4}{\rmdefault}{\mddefault}{\updefault}{\color[rgb]{0,0,0}u}%
} [lB] at  7.211 24.460
\linethickness=0pt
\putrectangle corners at  0.207 26.416 and  7.243 22.900
\endpicture}
 
\end{center}
 
 
\caption{\label{cap:bipart_dukaz}Cesty $P_{x}$ a $P_{y}$}
\end{figure}
 
 
Z toho ale plyne, že sled složený z úseků
\begin{enumerate}
\item $x$ do $z$ po $P_{x}$,
\item $z$ do $y$ po $P_{y}$,
\item $y$ do $x$ po hraně $\{ x,y\}$
\end{enumerate}
je kružnice liché délky, což je spor. Je to proto, že cesta $x\to z\to u\to z\to y$
je sudé délky, její úsek $z\to u\to z$, po kterém nejdeme, je však
také sudé délky, a tak i cesta $x\to z\to y$ musí být sudé délky.
Hrana $\{ x,y\}$ ji pak uzavírá na kružnici liché délky.
 
Zcela stejně ukážeme, že ani mezi vrcholy z $V_{2}$ nevede hrana.
 
Jestliže $G$ není souvislý, provedeme důkaz pro jeho komponenty $G^{(1)},...,G^{(m)}$
a získáme tak množiny $V_{1}^{(1)},...,V_{1}^{(m)}$ a $V_{2}^{(1)},...,V_{2}^{(m)}$.
Potom definujeme\begin{eqnarray*}
V_{1} & = & \bigcup_{j=1}^{m}V_{1}^{(j)}\\
V_{2} & = & \bigcup_{j=1}^{m}V_{2}^{(j)}.\end{eqnarray*}
 
\end{proof}
\begin{rem*}
Nechť $G=(V,E)$ je souvislý. Potom zobrazení $d:V\times V\mapsto\N_{0}$
definované jako $d(u,v)=$délka nejkatšího sledu z $u$ do $v$ je
metrika na množině vrcholů $v$. Číslo $d(u,v)$ nazýváme \textbf{vzdáleností}
vrcholů $u,v$ v grafu $G$.
\end{rem*}