Informatyka MIMUW

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:

$(*)$ Dla każdego zbioru $X$ o co najmniej $n$ elementach i dowolnego rozbicia

$\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$

• istnieje podzbiór $X_1\subseteq X-\lbrace x_0 \rbrace$ o mocy $\vert X_1 \vert={\sf R}_{r}\!( m-1,n )$, w którym dowolny podzbiór $(r-1)$-elementowy należy do $\mathscr{A}'_1$,

lub też

• istnieje podzbiór $X_2\subseteq X-\lbrace x_0 \rbrace$ o mocy $\vert X_2 \vert={\sf R}_{r}\!( m,n-1 )$, w którym dowolny podzbiór $(r-1)$-elementowy należy do $\mathscr{A}'_2$.

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:

• W $X_1$ istnieje podzbiór $X_{11}\subseteq X_1$, o mocy $\vert X_{11} \vert=m-1$, i którego każdy $r$-elementowy podzbiór należy do $\mathscr{A}_1$.

• W $X_1$ istnieje podzbiór $X_{12}\subseteq X_1$, o mocy $\vert X_{12} \vert=n$, i którego każdy $r$-elementowy podzbiór należy do $\mathscr{A}_2$.

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 )$.