Kaptam egy feladatot egyetemen diszkrét matematika tárgyból, a tanár azt mondta, ha megoldom ad egy vizsga ötöst. Valaki tud segíteni?

Gondolom d(i) az i-edik csúcs fokszáma.

Először néhány meggondolás, amik nem feltétlenül kellenek még a megoldáshoz:

Ha izomorf két gráf, akkor minden csúcsnak kell legyen egy párja a másik gráfban, aminek ugyanakkora a fokszáma. Vagyis Σd(i) egyforma kell legyen a két gráfban. (Ez csak szükséges feltétel!)

Ha a komplementerrel izomorf, akkor Σd(i) éppen a teljes gráf élszámának a fele kell legyen ezért. (Most nem fontos, de mivel a teljes gráf élszáma n(n-1)/2, ebből következik egyébként, hogy az ilyen "önmagával komplementer" gráfoknál n=4k vagy n=4k+1 lehet csak, hisz vagy n, vagy n-1 osztható kell legyen 4-gyel.)

Ez viszont már kell a megoldáshoz:

Ha az x-edik csúcsnak d(x) a fokszáma, akkor ugyanennek a csúcsnak a fokszáma a komplementer gráfban n-1-d(x). Mivel izomorf önmaga komplementerével, ezért vagy az van, hogy minden x-hez kell lennie az eredeti gráfban egy y csúcsnak, amire d(y) = n-1-d(x), vagy önmaga lesz a csúcs párja az izomorf gráfban.

Ha az x és y csúcsok felelnek meg egymásnak a komplementer gráfokban, akkor d(x)+d(y)=n-1, ha pedig saját magához rendelődik a csúcs, akkor d(x) = (n-1)/2 kell legyen.

Vagyis az átlagos fokszám kereken (n-1)/2

Páratlan számú csúcsa van a gráfnak, tehát muszáj legyen olyan csúcsa, ami önmagának a párja.

Már csak ki kell számolni, hogy mennyi az átlagos fokszám, és kész leszel. Azt rád bízom.