теория графов. свойства планарного графа

[aj2201]

Доказать, что в любом планарном графе (без петель и кратных ребер), имеющем не менее 4 вершин, найдутся хотя бы 4 вершины, степени которых не больше 5.

[paha]

aj2201 в сообщении #397370 писал(а):

имеющем не менее 4 вершин, найдутся хотя бы 4 вершины, степени которых не больше 5.

от противного: ну представьте себе полный граф с пятью вершинами)))

[VAL]

aj2201 в сообщении #397370 писал(а):

Доказать, что в любом планарном графе (без петель и кратных ребер), имеющем не менее 4 вершин, найдутся хотя бы 4 вершины, степени которых не больше 5.

Учтите, что сумма степеней вершин равна удвоенному числу ребер (лемма о рукопожатиях), соотношение Эйлера для связных планарных графов ($n+f-m=2$), а также тот факт, что каждая грань окружена не менее чем тремя ребрами.

[aj2201]

именно с учетом этого я смогла доказать что существуют по крайней мере 3 вершины

[VAL]

paha в сообщении #397382 писал(а):

aj2201 в сообщении #397370 писал(а):

имеющем не менее 4 вершин, найдутся хотя бы 4 вершины, степени которых не больше 5.

от противного: ну представьте себе полный граф с пятью вершинами)))

IMHO, так не проходит. Из того, что в графе степени всех вершин больше пяти, наличие подграфа изоморфного $K_5$ или хотя бы стягиваемого к $K_5$ так сразу не вытекает.

[paha]

VAL в сообщении #397386 писал(а):

а также тот факт, что каждая грань окружена не менее чем тремя ребрами.

я просто не в курсе... разве невложимость $K_5$ в плоскость не требует дополнительных соображений?

[aj2201]

в итоге я предположила, что есть три таких вершины, и пыталась прийти к противоречию

-- Пн янв 10, 2011 01:22:09 --

paha в сообщении #397389 писал(а):

VAL в сообщении #397386 писал(а):

а также тот факт, что каждая грань окружена не менее чем тремя ребрами.

я просто не в курсе... разве невложимость $K_5$ в плоскость не требует дополнительных соображений?

это следует из теоремы Понтрягина-Куратовского

[paha]

VAL в сообщении #397388 писал(а):

так сразу

ну, если грамотно "от противного" сформулировать (любые 4 вершины имеют степень не меньше 5), то вытекает

-- Пн янв 10, 2011 00:24:30 --

aj2201 в сообщении #397390 писал(а):

это следует из теоремы Понтрягина-Куратовского

вот я и говорю: разве доказательство этой теоремы в одну сторону так халявно получается?

[VAL]

aj2201 в сообщении #397387 писал(а):

именно с учетом этого я смогла доказать что существуют по крайней мере 3 вершины

Не понял!? У Вас же их по условию не менее четырех!

[paha]

VAL в сообщении #397394 писал(а):

Не понял!? У Вас же их по условию не менее четырех!

неправильно понятое "от противного"

[VAL]

paha в сообщении #397389 писал(а):

VAL в сообщении #397386 писал(а):

а также тот факт, что каждая грань окружена не менее чем тремя ребрами.

я просто не в курсе... разве невложимость $K_5$ в плоскость не требует дополнительных соображений?

Непланарность $K_5$ (так же как и $K_{3,3}$ доказывается легко, в пару строчек. Гораздо труднее доказывается, что во всяком непланарном графе обязательно есть подграф, стягиваемый либо к $K_5$, либо к $K_{3,3}$

[aj2201]

paha в сообщении #397391 писал(а):

любые 4 вершины имеют степень не меньше 5

но ведь если опровергать то получается
среди любых 4 вершин хотя бы одна имеет степень не меньше 6ти

[paha]

aj2201 в сообщении #397403 писал(а):

среди любых 4 вершин хотя бы одна имеет степень не меньше 6ти

Да, Вы правы, я поторопился... так этого достаточно! Опираясь на это найдите в графе пять вершин степени не меньше 5

[aj2201]

aj2201 в сообщении #397403 писал(а):

среди любых 4 вершин хотя бы одна имеет степень не меньше 6ти

если переформулировать получается есть не более трёх вершин(назвем их v, u, t) степени которых не больше 5ти
тогда сумма степеней всех вершин = $ 2q\geqslant 6(p-3)+deg(u)+deg(v)+deg(t)$

а из формулы эйлера следует что $q\leqslant 3(p-2 )$

-- Пн янв 10, 2011 01:57:11 --

получается нужно доказать что $deg(u)+deg(v)+deg(t)-6>0 $

[VAL]

Я почти привел готовое решение. Но у меня ощущение, что его не заметили
Попробую еще раз:

Можно считать, что граф связен (если это не так, достаточно рассмотреть каждый компонент в отдельности). Кроме того, можем считать, что у графа нет висячих вершин (если они есть, отбросим их вместе с инцидентными их ребрами) и вершин степени 2 (если они есть, каждую такую вершину вместе с двумя инцидентными ей ребрами заменим обним ребром).

Обозначим через n, m, f число, вершин, ребер и граней в плоской укладке графа.
Пусть степень каждой вершины (за исключением, разве что, трех) больше 5.
По лемме о рукопожатиях $\sum_{v\in V} deg(v)=2m$. Поэтому $2m\ge 6n-9$.
Учитывая, что каждая грань окружена не менее, чем тремя ребрами, а каждое ребро принадлежит максимум двум граням, имеем $2m \ge 3f$ или $4m\ge 6f$.
Складывая, получим $6m \ge 6(n+f)-9$, что противоречит соотношению Эйлера.