Élszám

Az élszámra vonatkozó Euler-tétel
Bizonyítás
Számoljuk össze az összes fokszámot! Mivel minden élnek két vége van, ezért mindegyik élt kétszer számoltam. Így bizonyítottuk a tételt. (Irányított gráfban minden egyes él kifok és befok.

Élszám: a gráf éleinek száma
Euler-tétel: fokszámok összege az élszám kétszerese;
véges gráfban a páratlan fokú pontok összege páros ...

A feszítőfák élszámai csak az input gráf csúcsszámától függnek, azaz azonosak. Így minimalizálás helyett maximálizálási kérdést vetve fel ugyanahhoz a problém'ahoz jutunk.

Tegyük fel, hogy q>0 és adott egy n szögpontú és maximális élszámú -et nem tartalmazó gráf. Ebben mindenképpen van teljes k-as, különben egy élt még hozzá tudnánk adni. Legyen A egy k elemű teljes ponthalmaz, B pedig a maradék pontok halmaza.

Két út áll előttünk: megpróbálhatjuk gráfunkat teljesen általánosan, szisztematikusan feldolgozni, azaz előállítjuk az adott pontok és élek alapján az összes lehetséges kombinációt, s kiválasztjuk a maximális élszámut.

Ekkor G -ben van olyan maximális élszámú párosítás, mely lefedi az összes F 0 által lefedett pontot.
24. feladat Ö M
(a) Konstruáljunk olyan gráfot, melyben egyetlenegy 1-faktor van, és minden fokszáma legalább k .

See also: Gráf, Bizonyítás, Kör, Összeg, Összefüggő