Egy 15*15-ös mátrix minden sorában és minden oszlopában nyolc 1-es és hét 0 szerepel. Hogyan bizonyítható, hogy van a determinánsának nemnulla kifejtési tagja?

Készítesz egy páros gráfot, aminek az egyik csúcsosztálya a 15 sorból, a másik csúcsosztálya pedig a 15 oszlopból áll. Egy sort és egy oszlopot pontosan akkor kötsz össze éllel, ha az adott sor és adott oszlop kereszteződési mezőjében 1-es szerepel a mátrixban. Az így kapott páros gráf 8-reguláris lesz, mivel minden sorban és minden oszlopban 8 db 1-es van. König tétele szerint r-reguláris páros gráfban van teljes párosítás, ezt felhasználva a páros gráfunkban van teljes párosítás, ami pont azt jelenti, hogy a mátrix determinánsának van nemnulla kifejtési tagja.