Самодополнительный граф

[marie-la]

Может ли в самодополнительном графе на $100$ вершинах существовать ровно одна вершина степени $50$?

Я даже не могу понять, правда или нет. Всего у этого графа $25\cdot99$ ребер, вершины делятся на пары, чтоб сумма степеней была 99. То есть одна вершина степени 50, одна вершина степени 49. И что с этим делать, не понимаю.

Ох, неужели так просто? Вершины степени 50 и 49 соединены либо нет одновременно в исходном и в дополнительном графе, значит в исходном и соединены, и не соединены одновременно? Придумала сейчас, пока писала.

[vpb]

Правильно придумали.