Ez utóbbi állítás igazolása: Vegyünk egy tetszőleges algoritmust és futassuk az algoritmust addig, míg a szomszédsági mátrix egyik elemét elolvassa. Ott egy 0-t vagy egy 1-et talál. Ettől függően az algoritmus esetleg különbözőképpen fut tovább, amíg egy újabb bitet el nem olvas és ekkor a futás további részét két további alesetre szakíthatjuk szét... Az algoritmus ezen struktúráját ``lerajzolva '' jutunk el a döntési fa fogalmához.
Az alábbi ábra egy példát mutat döntési fára.
Egy jó algoritmus esetén a döntési fa minden számítási ágán összegyűlik annyi információ, hogy a megoldandó probléma eldöntéséhez elég legyen.
Azt fogjuk igazolni, hogy minden helyes döntési fa mélysége n(n-1)/2.
Ehhez egy játékot vizsgálunk: Egy kérdező és egy válaszoló lesz a két játékos. A kérdező az ismeretlen illeszkedési mátrix egy-egy elemére kérdez rá és a válaszoló megmondja, hogy a kérdezett elem 0 vagy 1. A kérdező addig kérdez, amíg el nem tudja dönteni (az összegyűjtött információk alapján), hogy az ismeretlen gráfban van-e izolált pont. Belátjuk, hogy a válaszolónak van olyan stratégiája, hogy a kérdézőt n(n-1)/2 kérdésre kényszerítse.
A stratégia legyen a következő:
Ezekután nézzük meg az állításunk igazolását:
X(t) a kérdező-válaszoló protokol futásának t-edik időpillanatában azon csúcsok halmaza, amelyekre illeszkedik él a kérdező eddig kapott válaszai alapján. Az ismertetett válaszoló stratégia olyan, hogy X(t)-n belül nincs megkérdezetlen él.
Mindenekelőtt vizsgáljuk meg az X függvény néhány tulajdonságát. A kérdés megkezdése elótt az X halmaz értéke természetesen az üreshalmaz. Az első kérdés (legyen ez ``u és v összekötött?'') után az X halmaz értéke az u és v csúcskat tartalmazó halmaz (X(1)={u,v}). Az X függvény természetesen monoton, azaz t < s esetén X(t) részhalmaza (nem feltétlenül valódi részhalmaza) X(s)-nek.
Belátjuk, hogy amikor a kérdező tudja, hogy G-ben van-e izolált csúcs, akkor mindent megkérdezett, sőt az adódik, hogy az algoritmus végén az X halmaz a teljes csúcshalmaz.
Ez ellentmond a válaszoló strtégiájának. Vizsgáljuk meg, hogy hogyan változik az az Y(t) halmaz, amely azon csúcsokat tartalmazza, amelyek és v által tartalmazott párokat a kérdező megkérdezte (és feltételezésünk szerint 0, azaz ``nem összekötött'' választ kapott). Y(0) az üres halmaz. Feltételezésünk szerint az algoritmus végén az Y halmaz a V(G)-{v} halmaz. Y(t+1) vagy azonos Y(t)-vel vagy egyetlen egy csúccsal történő bővítése Y(t)-nek. (Azt is mondhatjuk, hogy a folytonossági és monoton tulajdonság egy diszkrét változatát teljesi;ti az Y függvény.) Az algoritmus végen az Y halmaz ``utoléri '' az X=(X-{v}) halmazt. Lesz a kérdezés folyamán az utolsó olyan időpillanat (legnagyobb t érték) amikor Y(t) nem tartalmazza X(t) halmazt. t választása miatt Y(t+1) tartalmazza X(t)-t. t-ről t+1-re ugorva (feltéve a t+1-edik kérdést) az Y halmaz legfeljebb egy elemmel nő (nőni is fog, hiszen utol kell érnie a nem csökkenő X halmazt). Ez csak úgy lehet, ha X(t+1) és Y(t+1) egyenlő. Továbbá X(t+1)=X(t) hiszen Y növekedéséhez szükségszerű, hogy az utolsó kérdés egy v-t tartalmazó pár legyen, amely kérdésre feltételezésünk szerint 0 választ kell kapnunk, azaz az X halmaz nem változik.
Y(t)-hez képest Y(t+1) nő, azaz a t+1-edik kérdés egy v-t tartalmazó pár volt: {v,v'} (Y(t+1)=Y(t)U{v'}). Mit csinál a válaszadó? A leírt stratégia alapján megnézi, hogy mi történne, ha ``összekötött''-et válaszolna (X(t+1)=X(t)U{v,v'}=X(t)U{v}). Ekkor meg kell vizsgálnia, hogy ezen halmazon belül minden csúcspár tesztelt-e. X(t)-n belül mindennek teszteltnek kell lenni. v és X(t) elemei által alkotott párok viszont Y(t+1)=X(t+1)=X(t) és az T halmaz definíciója miatt már teszteltek. A startégiánk viszont ekkor azt mondja, hogy a válaszoló 1-gyel váalszoljon. Ez ellentmond feltevésünknek.