Bevis av hörnklassarna A och B är lika stora.
Hej jag behöver hjälp med den här:
Antag att en bipartit graf har hörnklasser A och B och är k-reguljär, vilket innebär att alla hörn har samma grad . Visa att hörnklasserna A och B är lika stora.
Behöver du hjälp med själva frågan och att förstå begreppen? Eller att konstruera beviset?
Finns säkert ett bevis med hänvisning till andra satser men induktion borde inte vara så svårt.
Om k = 1 är hörnklasserna såklart lika stora.
Om k = 2 så kan vi ta alla noder i ena hörnklassen och stryka en av kanterna för att få k = 1, fallet, osv.
Man måste vara ganska noggrann i hur man formulerar induktionsstegen stegen och formulera "strykning" i matematikspråk. Så ett språkligt korrekt in induktionsbevis är inte så enkelt men själva logiken är det.
Förstår inte det och har aldrig läst om det här ämnet.
