W tym wykładzie spróbujemy odpowiedzieć na niektóre pytania typu: jak bardzo musi być liczny dany zbiór, by wystąpiła w nim pożądana przez nas konfiguracja. Widzieliśmy, że na aby mieć gwarancję, że \( \mathbf{G}=( V,E ) \) jest spójny, potrzeba by miał on więcej niż \( \vert V \vert\cdot(\vert V \vert-1)/2 \) krawędzi. Najprostszym jednak warunkiem tego typu jest Zasada Szufladkowa Dirichleta i następujące jej uogólnienie.
Twierdzenie 3.1 [Uogólniona Zasada Szufladkowa Dirchlet'a]
Dla dowolnej liczby \( q\in\mathbb{N} \), jeśli \( X=X_1\cup\ldots\cup X_t \) oraz \( \vert X \vert\geq (q-1)t+1 \), to dla któregoś \( i \) mamy \( \vert X_i \vert\geq q \).
Dowód
Wykorzystując założenia twierdzenia otrzymujemy następujące oszacowanie:
\( (q-1)t+1\leq\vert X \vert =\vert X_1\cup\ldots\cup X_t \vert \leq\vert X_1 \vert+\ldots+\vert X_t \vert \leq t\cdot \max_{i=1,\ldots, t}{\vert X_i \vert}. \)
Tak więc
\( (q-1)+\frac{1}{t}=\frac{(q-1)t+1}{t}\leq\max_{i=1,\ldots, t}{\vert X_i \vert}. \)
Ponieważ moce zbiorów \( X_i \) są liczbami całkowitymi otrzymujemy, że ta maksymalna musi wynosić co najmniej \( q \).
Uogólniona Zasada Szufladkowa wymusza, że któryś składnik podziału musi mieć co najmniej \( q \) elementów. Zasadę tę można uogólnić w ten sposób, by zadając najpierw ciąg liczb naturalnych \( q_1,\ldots,q_k \), w miejsce jednej liczby \( q \), i podział \( X=X_1\cup\ldots\cup X_t \) żądać by któryś składnik \( X_i \) był co najmniej \( q_i \) elementowy. Otrzymujemy w ten sposób Zasadę Podziałową. Przy wszystkich \( q_i=q \) jest to Twierdzenie 3.1.
Twierdzenie 3.2 [Zasada podziałowa]
Niech \( q_1,\ldots,q_k \) będzie ciągiem liczb naturalnych. Jeśli
\( X=X_1\cup\ldots\cup X_t\quad\textrm{oraz}\quad\vert X \vert>( \sum_{i=1}^t{q_i} )-t, \)
to \( \vert X_i \vert\geq q_i \) dla pewnego \( i \).
Dowód
Załóżmy, wbrew tezie twierdzenia, że jakiś \( X \) o mocy \( \vert X \vert\geq( \sum_{i=1}^t{q_i} )-t+1 \) rozkłada się na sumę \( X=X_1\cup\ldots\cup X_t \), przy czym każdy składnik ma moc \( \vert X_i \vert\leq q_i-1 \). Wtedy nierówność dwu skrajnych liczb w
\( ( \sum_{i=1}^t{q_i} )-t+1\leq\vert X \vert =\vert X_1\cup\ldots\cup X_t \vert \leq\vert X_1 \vert+\ldots+\vert X_t \vert \leq \sum_{i=1}^t( q_i-1 ), \)
stoi w sprzeczności, i kończy dowód.
Można też pytać o liczbę wierzchołków w grafie wymuszających jedną z pożądanych konfiguracji.
Twierdzenie 3.3 [F.P.Ramsey 1930]
Dla dowolnej liczby \( r\in\mathbb{N} \), jeżeli tylko graf prosty \( \mathbf{G} \) posiada co najmniej \( 2^{2r-1} \) elementów, to \( \mathbf{G} \) zawiera jako podgraf indukowany klikę \( \mathcal{K}_{r} \) lub antyklikę \( \mathcal{A}_{r} \).
Dowód
Niech \( n:=\vert \mathbf{G} \vert\geq 2^{2r-1} \). Dla każdego \( x\in{\sf V}\!(\mathbf{G}) \) definiujemy dwa zbiory: odpowiednio zbiór sąsiadów wierzchołka \( x \) oraz zbiór elementów nie będących sąsiadami \( x \):
\( \begin{align*} {\sf N}_{\mathbf{G}}\!( x ) & =\lbrace y\in{\sf V}\!(\mathbf{G}):\ xy\in{\sf E}\!(\mathbf{G}) \rbrace, \\ {\sf A}_{\mathbf{G}}\!( x ) & =\lbrace y\in{\sf V}\!(\mathbf{G}):\ xy\notin{\sf E}\!(\mathbf{G}) \rbrace. \end{align*} \)
Zdefiniujemy ciąg grafów \( \mathbf{G}_0, \mathbf{G}_1, \ldots, \mathbf{G}_{2r-1} \). Niech \( \mathbf{G}_0:=\mathbf{G} \). Wybierzmy jakiś element \( x_1\in{\sf V}\!(\mathbf{G}) \) i zdefiniujmy podgraf \( \mathbf{G}_1 \) grafu \( \mathbf{G}_0=\mathbf{G} \) w następujący sposób
\( \mathbf{G}_1 = \left\{ \begin{array} {ll} {\mathbf{G}_0}|_{{\sf N}_{{\mathbf{G}_0}}\!( x_1 )}, & \textrm{jeżeli}\ \vert {\sf A}_{\mathbf{G}_0}\!( x_1 ) \vert\leq\vert {\sf N}_{\mathbf{G}_0}\!( x_1 ) \vert, \\ {\mathbf{G}_0}|_{{\sf A}_{\mathbf{G}_0}\!( x_1 )}, & \textrm{w przeciwnym wypadku.} \end{array} \right . \)
Zauważmy, że \( \vert {\sf V}\!(\mathbf{G}_1) \vert\geq2^{2r-2} \). Następnie wybieramy dowolny element \( x_2\in{\sf V}\!(\mathbf{G}_1) \) i analogicznie definiujemy \( \mathbf{G}_2 \). W ogólności dla \( i=1,\ldots,2r-1 \) graf \( \mathbf{G}_i \) definiujemy poprzez
\( \mathbf{G}_i = \left\{ \begin{array} {ll} {\mathbf{G}_{i-1}}|_{{\sf N}_{\mathbf{G}_{i-1}}\!( x_i )}, & \textrm{jeżeli}\ \vert {\sf A}_{\mathbf{G}_{i-1}}\!( x_i ) \vert\leq\vert {\sf N}_{\mathbf{G}_{i-1}}\!( x_i ) \vert, \\ {\mathbf{G}_{i-1}}|_{{\sf A}_{\mathbf{G}_{i-1}}\!( x_i )}, & \textrm{w przeciwnym wypadku,} \end{array} \right . \)
gdzie \( x_{i-1} \) jest dowolnie wybranym elementem ze zbioru \( {\sf V}\!(\mathbf{G}_{i-1}) \). Każdy kolejny graf zmniejszy się o co najwyżej połowę elementów, tak więc cały czas zachowana jest własność
\( \vert {\sf V}\!(\mathbf{G}_i) \vert\geq2^{2r-(i+1)}. \)
To z kolei implikuje, że dla \( i\leq 2r-1 \) zbiór \( {\sf V}\!(\mathbf{G}_i) \) jest niepusty, co pozwala zawsze na wybór kolejnych \( 2r-) \) wierzchołków \( x_1,\ldots,x_{2r-1} \) potrzebnych do zdefiniowania kolejnych grafów \( \mathbf{G}_i \). Każdy element \( x_i \) albo sąsiaduje ze wszystkimi wierzchołkami grafu \( \mathbf{G}_i \) albo też nie jest połączony krawędzią z żadnym z wierzchołków w \( \mathbf{G}_i \). Tak więc w ciągu \( x_1,\ldots,x_{2r-1} \) można wyróżnić podciąg \( x_{j_1},\ldots,x_{j_s} \) elementów pierwszego typu oraz podciąg \( x_{l_1},\ldots,x_{l_t} \) elementów drugiego typu. Element \( x_{j_1} \) sąsiaduje z każdym elementem z \( {\sf V}\!(\mathbf{G}_{j_1}) \), a więc także z każdym \( x_{j_i} \) dla \( i\geq 2 \). Z kolei \( x_{j_2} \) sąsiaduje z każdym elementem z \( {\sf V}\!(\mathbf{G}_{j_2}) \), a więc także z każdym \( x_{j_i} \) dla \( i\geq 3 \) i tak dalej. Zatem zbiór wierzchołków \( \lbrace x_{j_1},\ldots,x_{j_s} \rbrace \) w grafie \( \mathbf{G} \) indukuje \( s \)-elementową klikę. Analogicznie \( \mathbf{G}|_{\lbrace x_{l_1},\ldots,x_{l_t} \rbrace} \) jest \( t \)-elementową antykliką. Oczywiście \( s+t=2r-1 \). Tak więc na mocy Uogólnionej Zasady Szufladkowej Dirichlet'a otrzymujemy, że \( s\geq r \) albo \( t\geq r \), co kończy dowód.
Zauważmy, że zarówno Zasadę Podziałową (Twierdzenie 3.2), jak i Twierdzenie 3.3 można wypowiedzieć w tym samym języku. Niech \( \mathscr{P}_{r}\!( X ) \) będzie rodziną \( r \)-elementowych podzbiorów zbioru \( X \). Tak więc pokrycie \( X=X_1\cup\ldots\cup X_k \) to nic innego jak pokrycie rodziny \( \mathscr{P}_{1}\!( X )=\mathscr{A}_1\cup\ldots\cup\mathscr{A}_k \), gdzie \( \mathscr{A}_i=\lbrace \lbrace x \rbrace:\ x\in X_i \rbrace \). Oznacza to, że w Zasadzie Podziałowej żądamy podzbioru \( Y\subseteq X \), dla którego istnieje \( i \), takie że \( \vert Y \vert= q_i \) oraz że dowolny singleton zawarty w \( Y \) należy do \( \mathscr{A}_i \).
Z drugiej strony graf prosty z Twierdzenia 3.3 to para \( \mathbf{G}=( V,E ) \), gdzie \( E\subseteq\mathscr{P}_{2}\!( V ) \). Daje to więc podział \( \mathscr{P}_{2}\!( V )=E\cup( \mathscr{P}_{2}\!( V )- E ) \). Żądanie \( r \)-elementowej kliki jest żądaniem \( r \)-elementowego podzbioru \( K \) zbioru \( V \) takiego, że dowolna "krawędź" pomiędzy elementami w \( K \), czyli dowolny element \( \mathscr{P}_{2}\!( K ) \), jest \( E \). Analogicznie poszukiwana antyklika jest po prostu podzbiorem \( A \) zbioru \( V \) takim, że \( \mathscr{P}_{2}\!( A )\subseteq \mathscr{P}_{2}\!( V )- E \).
Następne twierdzenie jest uogólnieniem Twierdzeń 3.1, 3.2, oraz 3.3. Warto zauważyć, że poniższe twierdzenie Ramsey'a nie podaje niestety minimalnego oszacowania na moc zbioru \( X \). Nie podamy też w tym wykładzie jego dowodu.
Twierdzenie 3.4 [F. P. Ramsey 1930]
Dla dowolnych \( r,t\in\mathbb{N} \) oraz dla dowolnego ciągu liczb naturalnych \( q_1,\ldots, q_t \) istnieje liczba \( n \) o następującej własności:
\( \mathscr{P}_{r}\!( X )=\mathscr{A}_1\cup\ldots\cup\mathscr{A}_t \), istnieje podzbiór \( Y \) zbioru \( X \) o co najmniej \( q_i \) elementach taki, że \( \mathscr{P}_{r}\!( Y )\subseteq \mathscr{A}_i \) przy pewnym \( i=1,\ldots,t \).
Liczba Ramseya \( {\sf R}_{r}\!( q_1,\ldots,q_t ) \) to najmniejsza taka liczba \( n\in\mathbb{N} \), dla której spełniony jest warunek \( (*) \).
Szczególnym przypadkiem jest \( {\sf R}\!( q_1,\ldots,q_t ):={\sf R}_{2}\!( q_1,\ldots,q_t ) \).
Wielu matematyków fascynowały i nadal fascynują liczby Ramsey'a. W szczególności dlatego, że bardzo mało nich wiemy. Poniższa tabela przedstawia dotychczasową wiedzę na temat liczb \( {\sf R}_{2}\!( m,n ) \). Jak widać nawet dla małych wartości \( n \) oraz \( m \), dokładne wartości liczb \( {\sf R}_{2}\!( m,n ) \) nie są znane.
\( \begin{array} {|c||c|c|c|c|c|c|c|c|} \hline n\downarrow\ marrow & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline \hline 2 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 3 & & 6 & 9 & 14 & 18 & 23 & 28\leq\ldots\leq29 & 36 \\ \hline 4 & & & 18 & 25\ldots\leq29 & 34\leq\ldots\leq36 & & & \\ \hline 4 & & & & 42\leq\ldots\leq55 & 57\leq\ldots\leq94 & & & \\ \hline 4 & & & & & 102\leq\ldots\leq178 & & & \\ \hline \end{array} \)
Pomimo, że nie znamy dokładnych wartości liczb Ramsey'a \( {\sf R}\!( q_1,\ldots,q_t ) \) przedstawimy kilka twierdzeń przybliżających te liczby.
Uwaga
Wartość liczby Ramsey'a z indeksem \( r=1 \) jest opisana w Zasadzie Podziałowej (Twierdzenie 3.2). Zasadę tę można przeformułować jako:
\( {\sf R}_{1}\!( q_1,\ldots,q_t )=( \sum_{i=1}^t{q_i} )-t+1. \)
Dla liczb Ramsey'a z indeksem \( r=2 \) podamy, bez dowodu, następujące oszacowanie górne.
Twierdzenie 3.5
\( {\sf R}\!( q_1,\ldots,q_t )\leq\frac{t^{q_1+\ldots+q_t-2t+1}-1}{t-1}+1. \)
Z uwagi na Twierdzenie 3.3, ważną rolę odgrywają liczby Ramsey'a postaci \( {\sf R}_{r}\!( m,n ) \) a w szczególności \( {\sf R}\!( m,n )={\sf R}_{2}\!( m,n ) \). O nich możemy powiedzieć już trochę więcej w tym wykładzie.
Twierdzenie 3.6
Dla dowolnych \( m, n \geq 2 \) oraz \( r \geq 1 \) mamy:
\( {\sf R}_{r}\!( m,n )\leq {\sf R}_{{r-1}}\!( {\sf R}_{r}\!( m-1,n ),{\sf R}_{r}\!( m,n-1 ) )+1. \)
Dowód
Niech \( X \) będzie zbiorem o \( {\sf R}_{{r-1}}\!( {\sf R}_{r}\!( m-1,n ),{\sf R}_{r}\!( m,n-1 ) )+1 \) elementach, \( x_0\in X \) i \( X'=X-\lbrace x_0 \rbrace \). Wtedy każdy podział \( \mathscr{P}_{r}\!( X )=\mathscr{A}_1\cup\mathscr{A}_2 \) indukuje podział \( \mathscr{P}_{r-1}\!( X' )=\mathscr{A}'_1\cup\mathscr{A}'_2 \), gdzie
\( \begin{align*} \mathscr{A}'_1 & = \lbrace A-\lbrace x_0 \rbrace :\ A\in\mathscr{A}_1\ \ & \ x_0\in A \rbrace, \\ \mathscr{A}'_2 & = \lbrace A-\lbrace x_0 \rbrace :\ A\in\mathscr{A}_2\ \ & \ x_0\in A \rbrace. \end{align*} \)
Ponieważ moc \( \vert X-\lbrace x_0 \rbrace \vert \) realizuje liczbę Ramsey'a \( {\sf R}_{{r-1}}\!( {\sf R}_{r}\!( m-1,n ),{\sf R}_{r}\!( m,n-1 ) ) \), to w zbiorze \( X-\lbrace x_0 \rbrace \)
lub też
Bez straty ogólności załóżmy, że zachodzi przypadek pierwszy. Z definicji liczb Ramsey'a oraz z faktu, że \( \vert X_1 \vert={\sf R}_{r}\!( m-1,n ) \) otrzymujemy następujące dwa przypadki, których analiza jest podobna:
Z uwagi na symetrię przeanalizujemy jedynie pierwszy przypadek. Niech \( A\subseteq X_{11}\cup\lbrace x_0 \rbrace \) ma \( r \)-elementów. Jeśli \( x_0\not\in A \), to \( A \) zawiera się w \( X_{11} \), i co za tym idzie, \( A \) należy do \( \mathscr{A}_1 \). Jeśli zaś \( x_0\in A \), to \( A-\lbrace x_0 \rbrace \) jest \( (r-1) \)-elementowym podzbiorem zbioru \( X_1 \). A więc należy do \( \mathscr{A}'_1 \). Z definicji rodziny \( \mathscr{A}'_1 \) otrzymujemy, że i w tym przypadku \( A \) należy do \( \mathscr{A}_1 \).
W konsekwencji otrzymujemy, że w \( X \) istnieje podzbiór \( Y_1 \) (w rozpatrzonym przypadku jest to \( X_{11}\cup\lbrace x_0 \rbrace \)), którego każdy \( r \)-elementowy podzbiór należy do \( \mathscr{A}_1 \), lub też w \( X \) istnieje podzbiór \( Y_2 \) (w rozpatrzonym przypadku jest to \( X_{12} \)), którego każdy \( r \)-elementowy podzbiór należy do \( \mathscr{A}_2 \). Ponieważ zbiór \( X \) ma moc \( {\sf R}_{{r-1}}\!( {\sf R}_{r}\!( m-1,n ),{\sf R}_{r}\!( m,n-1 ) )+1 \), to
\( {\sf R}_{r}\!( m,n )\leq {\sf R}_{{r-1}}\!( {\sf R}_{r}\!( m-1,n ),{\sf R}_{r}\!( m,n-1 ) )+1. \)
Twierdzenie 3.7
Dla dowolnych \( m, n \geq 2 \)
\( {\sf R}\!( m,n )\leq {{m+n-2}\choose{m-1}}. \)
Dowód
Dowód przeprowadzimy indukcyjnie ze względu na \( n \) oraz \( m \). Dla \( n=2 \) zachodzi równość
\( {\sf R}\!( m,2 )=m={{m}\choose{1}}={{m+n-2}\choose{m- 1}}, \)
a dla \( m=2 \) zachodzi równość
\( {\sf R}\!( 2,n )=n={{n}\choose{1}}={{m+n-2}\choose{m-1}}. \)
Przejdźmy więc do przypadku, gdy \( n,m>2 \). Na mocy założenia indukcyjnego mamy:
\( {\sf R}\!( m-1,n )\leq{{m+n-3}\choose{m-2}},\quad{\sf R}\!( m,n-1 )\leq{{m+n-3}\choose{m-1}}. \)
Dla \( r=2 \) Twierdzenie 3.6 mówi, że
\( {\sf R}_{2}\!( m,n )\leq{\sf R}_{1}\!( {\sf R}_{2}\!( m-1,n ),{\sf R}_{2}\!( m,n-1 ) )+1 = {\sf R}_{2}\!( m-1,n ) + {\sf R}_{2}\!( m,n-1 ). \)
Tak więc
\( \begin{align*} {\sf R}\!( m,n ) & \leq{\sf R}\!( m-1,n ) + {\sf R}\!( m,n-1 ) \\ & \leq{{m+n-3}\choose{m-2}}+{{m+n-3}\choose{m-1}} \\ & ={{m+n-2}\choose{m-1}}, \end{align*} \)
co kończy dowód.
Przejdziemy teraz do szacowania liczb Ramsey'a od dołu. Do tego celu potrzebować będziemy następującej definicji.
Dwukolorowalna rodzina \( n \)-elementowych podzbiorów zbioru \( X \) to rodzina \( \mathscr{X}\subseteq\mathscr{P}_{n}\!( X ) \), dla której istnieje takie kolorowanie elementów zbioru \( X \) dwoma kolorami tak, by żaden zbiór \( A\in\mathscr{X} \) nie składał się z elementów tego samego koloru.
Innymi słowy, rodzina \( \mathscr{X} \) jest dwukolorowalna, jeśli istnieje podzbiór \( C\subseteq X \) taki, że
\( \emptyset\neq C \cap A \neq A\quad\textrm{dla każdego}\ A\in\mathscr{X}. \)
Twierdzenie 3.8
Niech \( n\geq 1 \) oraz \( \mathscr{X}\subseteq \mathscr{P}_{n}\!( X ) \). Jeśli \( \vert X \vert < 2^{n-1} \), to rodzina \( \mathscr{X} \) jest dwukolorowalna.
Dowód
Niech \( m:=\vert X \vert \). Policzmy pary w zbiorze
\( \mathscr{A}=\lbrace ( A,C ):\ A\in\mathscr{X} \mbox{ i } ( A\subseteq C \mbox{ albo } A\subseteq X- C ) \rbrace. \)
Liczba podzbiorów zbioru \( X \) zawierających \( A \) jest równa liczbie podzbiorów zbioru \( X \) rozłącznych z \( A \), i ponieważ \( \vert A \vert=n \), to wynosi ona \( 2^{m-n} \). Zatem
\( \vert \mathscr{A} \vert=\vert \mathscr{X} \vert\cdot 2^{m-n+1}. \)
Niech teraz rodzina \( \mathscr{X} \) nie będzie dwukolorowalna, czyli dla każdego zbioru \( C\subseteq X \) istnieje \( A\in\mathscr{X} \) taki, że \( A\subseteq C \) albo \( A\subseteq X- C \). Tak więc par w \( \mathscr{A} \) jest co najmniej tyle co podzbiorów \( C\subseteq X \), a więc
\( 2^m\leq\vert \mathscr{A} \vert=\vert \mathscr{X} \vert\cdot 2^{m-n+1}, \)
skąd natychmiast
\( \vert \mathscr{X} \vert\geq 2^{n-1}. \)
Twierdzenie 3.9 [P. Erd{o}s 1947]
\( {\sf R}\!( n,n )\geq n2^{n/2}( \frac{1}{e\sqrt{2}}-o( 1 ) ). \)
Dowód
Niech \( Y \) będzie zbiorem o \( m:={\sf R}\!( n,n ) \) elementach. Połóżmy
\( X=\mathscr{P}_{2}\!( Y ) \)
i dalej
\( \mathscr{X}=\lbrace \mathscr{P}_{2}\!( A ):\ A\in\mathscr{P}_{n}\!( Y ) \rbrace. \)
Wtedy \( \mathscr{X}\subseteq\mathscr{P}_{{n\choose2}}\!( X ) \). Ponieważ \( Y \) ma \( {\sf R}\!( n,n ) \) elementów, to rodzina \( \mathscr{X} \) nie jest dwukolorowalna, tak więc na mocy Twierdzenia 3.8 trzymujemy:
\( \vert \mathscr{X} \vert\geq 2^{{n\choose 2}-1} \)
Z kolei definicja rodziny \( \mathscr{X} \) daje \( \vert \mathscr{X} \vert={m\choose n} \), a więc
\( \frac{m^n}{n!} \geq\frac{m\cdot( m-1 )\cdot\ldots\cdot( m-n+1 )}{n\cdot( n-1 )\cdot\ldots\cdot 1} ={m\choose n} =\vert \mathscr{X} \vert \geq 2^{{n\choose 2}-1} \)
Otrzymujemy więc, że
\( m^n\geq n!\cdot2^{( n^2-n-2 )/2}, \)
co z kolei implikuje, że
\( m \geq\sqrt[n]{n!}\cdot2^{n/2}\cdot2^{-1/2}\cdot2^{-1/n} \geq\sqrt[n]{n!}\cdot2^{n/2}( \frac{1}{\sqrt{2}}-o( 1 ) ). \)
Oszacowanie Sterlinga na \( n! \) daje
\( \sqrt[n]{n!} =n( \frac{\sqrt[2n]{2n}\cdot\sqrt[2n]{\pi}}{e}+o( 1 ) ) =n( \frac{1}{e}+o( 1 ) ). \)
i w konsekwencji otrzymujemy:
\( {\sf R}\!( n,n )=m \geq\sqrt[n]{n!}\cdot2^{n/2}( \frac{1}{\sqrt{2}}-o( 1 ) ) \geq n\cdot2^{n/2}( \frac{1}{e\sqrt{2}}-o( 1 ) ). \)
Twierdzenie 3.3 ma jeszcze inne ciekawe uogólnienie, pozwalające na wyszukiwanie zadanych uprzednio podgrafów w grafie macierzystym.
Twierdzenie 3.10 [W. Deuber 1974]
Dla dowolnych dwóch grafów prostych \( \mathbf{H}_1 \) oraz \( \mathbf{H}_2 \) istnieje graf prosty \( \mathbf{G} \) taki, że jakkolwiek nie podzielimy zbioru krawędzi \( {\sf E}\!(\mathbf{G}) \) na zbiory \( E_1,E_2 \), to \( \mathbf{H}_1 \) będzie podgrafem indukowanym grafu \( ( {\sf V}\!(\mathbf{G}),E_1 ) \) lub \( \mathbf{H}_2 \) będzie podgrafem indukowanym grafu \( ( {\sf V}\!(\mathbf{G}),E_2 ) \).