Задача от Теория на графите

[mrgray]

Как се доказва, при граф (simple graph) с брой на върхове n > 2, че съществуват винаги поне 2 върха с еднакъв брой връзки?

[martin123456]

имаме n върха. всеки от тях има 0,1,2,...,n-1 връзки. да доп че няма два с равен брой връзки. значи връзките на всички върхове са точно 0,1,..,n-1. значи има връх зус n-1 връзки и връх с 0 връзки - невъзможно

[mrgray]

мерси много