Лемма о рукопожатии с тремя людьми?

Лемма о рукопожатии утверждает, что в неориентированном графе четное число вершин должно иметь нечетную степень.

Однако 3 человека пожимают друг другу руки, 6 рукопожатий или по два с каждым. Значит, нет вершин с нечетной степенью.

Верна ли лемма о рукопожатии, потому что 0 четен и нет вершин нечетной степени?

Я не сомневаюсь, что лемма верна, просто думаю, что упускаю что-то действительно очевидное.


algorithm math undirected-graph graph-theory vertices
person user1768079    schedule 23.10.2016    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Верна ли лемма о рукопожатии, потому что 0 четен и нет вершин нечетной степени?

да. Так как все 3 вершины четной степени, то вершин нечетной степени нет.

Вы абсолютно правы. То же самое и в случае, когда люди = 1.

person Am_I_Helpful    schedule 23.10.2016
comment
Спасибо, я видел вашу опечатку, но я сделал аналогичную опечатку, когда задавал свой вопрос. - person user1768079; 23.10.2016
comment
@user1768079 user1768079 - Надеюсь, вам это тоже понятно логически. An even number of people must have shaken an odd number of other people's hands --- что можно проверить и логически. - person Am_I_Helpful; 23.10.2016
comment
Мне было ясно, я просто не был уверен, что я что-то упускаю в таких случаях. Я подумал, может быть, я неправильно понял определение чего-то. Во всех примерах, которые мне дали, были показаны графы без цикла, которые включали каждую вершину или имели какое-то другое условие, отличающее его от графа с нечетным числом вершин, имеющих одинаковые четные степени. - person user1768079; 23.10.2016
comment
@user1768079 - Хорошо, что ты решил спросить об этом здесь. Это показывает, что вы любознательны. Так держать! Удачи. - person Am_I_Helpful; 23.10.2016