Лема 2

Доказателства. Върховете на графика, състояща се от ръбове и върхове на фиксиран многоъгълник, имат еднаква степен. Обозначаваме тази степен с x. Нека y е броят на страните на лице на този многоъгълник. Получаваме системата от уравнения

.

Тъй като x, y  3 и в случая x, y  4, неравенството е изпълнено, тогава са възможни следните случаи: x = 3 или y = 3.

Да разгледаме случая x = 3:

.

x = 3, y = 3,;

x = 3, y = 4,;

x = 3, y = 5, .

По същия начин x = 4, x = 5 за y = 3.

§4.7. Упражнява Графични свойства

Всички графики се приемат за прости. Графиките се наричат ​​изоморфни, ако между множествата на техните върхове има биекция f, така че ръбът  е ръбът.

Докажете, че графиката има четен брой върхове с нечетни градуси.

Когато студентите се срещнаха, се извършиха 15 ръкостискания, трима души направиха по 4 ръкостискания, а останалите - 3. Колко ученици имаше?.

Може ли да има група от 23 души, всеки от които е запознат с още петима?

5 души участват в състезанието по шах в кръг. Всички, с изключение на Иванов и Петров, изиграха различен брой игри. Колко игри изиграха Иванов и Петров?

Възможно ли е да се начертае графика K6, без да се откъсва моливът с отстранен един ръб?.

Намерете броя на двойки неизоморфни графики с 2 върха на степен 2, 2 върха на степен 3 и 2 върха на степен 4. Останалите върхове са на степен 0.

Намерете броя на двойно неизоморфни графики с 3 върха на степен 2, 3 върха на степен 3 и 3 върха на степен 4. Останалите върхове са на степен 0.

Докажете, че в обикновена графика с поне два върха винаги има два върха с еднаква степен.

---