Feladat: Legyen M egy n×n-es táblázat elemei úgy vannak kitöltve, hogy minden sora különböző. Bizonyítsuk be, hogy M-nek van olyan oszlopa, hogy ennek elhagyása után is megmaradjon ezen tulajdonsága, azaz soroai különbözők.
Megjegyzés: Táblázatunk négyzetes. Ez egy fontos feltétel: (n+1)×n-es táblázat esetén az állítás nem igaz. Ehhez i=1,2,...,n esetén az i-edik sor i-edik pozíciójába tegyünk egy 1-est. Az összes többi elem legyen 0. Az utolsó sor csupa 0-t tartalmaz, ami különbözik az összes többi sortól. Az első n sort a bennük lévő 1-es pozíciója különbözteti meg. Ha viszont egy oszlopot törlünk, akkor az egyik 1-est elhagyjuk, csupa 0 sorrá válik, ami így egyenlő lesz az utolsó sorral.
Megoldás: Indirekten bizonyítunk. Tegyük fel, hogy M feltételeinket kielégítő mátrix, de tetszőleges oszlopát elhagyva lesz két azonos sora. Tegyük fel, hogy az i-edik oszlop elhagyásával az ai-edik és bi-edik sor azonossá válik (i=1,2,...,n). Természetesen ai különbözik bi-től (feltehető, hogy ai< bi), de gondolkodás nélkül nem zárhatjuk ki, hogy i és j különbözősége esetén az {ai,bi} és {aj,bj} párok azonosak legyenek.
Megjegyzés: A megoldásunkhoz nem lényeges, de kevés gondolattal láthatjuk, hogy i és j különbözősége esetén {ai,bi} és {aj,bj} halmazok különbözőek. Valóban, ha ai=aj és bi=bj, akkor az ai-edik és bi-edik sor azonos volna, ami ellentmond a feltevésünknek. A két sor azonossága az i-edik pozíciótól eltérő helyeken {ai,bi} definíciójából adódik, a j--edik pozíciótól eltérő helyen a {aj,bj} definíciójából adódik. A bizonyítás ezen egyszerű észrevétel egy kissé általánosabb alakján múlik.
Definiáljuk a következő GM gráfot. Csúcshalmaza {1,2,...,n}, azaz a sorindexek halmaza. Az élek e1, e2,...,en lesz, ahol az ei él a {ai,bi} párt köti össze. Nyilvánvaló, hogy gráfunk nem tartalmaz hurokélt. Előző megjegyzésünk azzal ekvivalens, hogy GM-ben nincsenek párhuzamos élek. A bizonyítás `lelke ' a következő lemma.
Lemma: GM-ben nincs kör.
A lemmából valóban következik az álítás. Indirekt bizonyítási sémánk miatt ellentmondáshoz kell jutnunk. Az ellentmondás abból ered, ogy egy n pontú, n élű gráfnak tartalmaznia kell kört. Amit igazolunk, az az, hogy ha egy gráf nem tartalmaz kört, akkor kevesebb éle van mint csúcsa. Valóban, ha egy gráf nem tartalmaz kört akkor minden komponense összefüggő körmentes gráf, azaz fa. Tudjuk, hogy fák élszáma eggyel kevesebb csúcsszámuknál, speciálisan élszámuk kisebb mint pontszámuk. Azaz egy körmentes gráf mindegyik komponensében kevesebb él van mint csúcs, ami így az egész gráfra igaz.
Lemma bizonyítása: Tegyük fel, hogy C egy kör a GM gráfban. GM nem tartalmaz hurokélt, így C-nek van két különböző pontja: x és y. Ez a két pont ké különböző ívre osztja C-t: I-re és J-re. Bármelyiket bejárva x-ből y-ba jutunk. Az x és y csúcsok az M mátrix két sorát jelölik. Belátjuk, hogy ez a két sor azonos, ami nem lehet az M-re tett feltételünkből. A két sor azonosságához ki kell választanunk egy tetszőleges pozíciót és igazolnunk kell, hogy ebben azonosak. A kiválasztott pozíció azonosítható egy oszloppal M-ben és így egy e éllel a GM gráfban. I vagy J ívek egyike nem tartalmazza ezt az élt (esetleg egyik sem). Egy ilyen e-t elkerülő ívet járjunk be és figyeljúk meg, hogy a bejárt csúcsok sorai hogyan változnak. Eredőben x-ből y-ba változik a figyelt sor. Másrészt minden lépésnél a sor változása csak egy pozícióra szorítkozik (lásd GM éleinek definícióját) és választásunk miatt a kinézett pozíciót egyik változás sem érinti. Ez mutatja a bizonyítandót.