Треугольник как подграф

@zelenoederevo · Регистрация: 17.11.2014

Author24 — интернет-сервис помощи студентам

Пускай G — граф с n вершинами, каждый степени не больше n/2. Нужно доказать, что граф содержит треугольник (как подграф).
Спасибо!

@Alamira · 07.01.2015, 09:10

Странно... Возьмем граф на трех вершинах. По условию их степени равны 1 или 0. И какой тут треугольник?

@zelenoederevo · 07.01.2015, 09:32 **[ТС]**

Ой, там в задании:" каждый степени больше чем n/2", извините, Alamira.

@Alamira · 07.01.2015, 12:35

Рассмотрим самый "неудобный" случай: степени всех вершин графа равны n/2+1 (оговорюсь, что здесь можно еще порассуждать на тему суммы степеней вершин графа). Выберем произвольную вершину, пометим ее А. В ее окружение входит n/2+1 смежных с ней вершин исходного графа. Выберем одну из них, пометим ее В. У нас есть уже две вершины, связанные ребром. Нужно показать, что можно найти третью вершину С, смежную с двумя исходными. Эту третью нужно выбирать из пересечения окружений двух ранее выбранных вершин. Осталось показать, что пересечение это не пусто. В окружение как вершины А, так и вершины В входят по n/2+1 вершины графа порядка n. (n/2+1) + (n/2+1) = n+2 > n. Это значит, у А и В есть как минимум 2 вершины, смежные с ними двумя. Из них и выберем С.

Байт · 07.01.2015, 14:32

Тут даже имеет место более сильное утверждение: Каждое ребро входит в треугольник.

@zelenoederevo 2 / 2 / 0 Регистрация: 17.11.2014 Сообщений: 48
		1
	Треугольник как подграф 07.01.2015, 01:34. Показов 1669. Ответов 4 Метки нет (Все метки) Пускай G — граф с n вершинами, каждый степени не больше n/2. Нужно доказать, что граф содержит треугольник (как подграф). Спасибо! 0

@Alamira 163 / 151 / 36 Регистрация: 04.11.2014 Сообщений: 303
	07.01.2015, 09:10	2
	Странно... Возьмем граф на трех вершинах. По условию их степени равны 1 или 0. И какой тут треугольник? 0

@zelenoederevo 2 / 2 / 0 Регистрация: 17.11.2014 Сообщений: 48
	07.01.2015, 09:32 [ТС]	3
	Ой, там в задании:" каждый степени больше чем n/2", извините, Alamira. 0

@Alamira 163 / 151 / 36 Регистрация: 04.11.2014 Сообщений: 303
	07.01.2015, 12:35	4
	Сообщение было отмечено zelenoederevo как решение Решение Рассмотрим самый "неудобный" случай: степени всех вершин графа равны n/2+1 (оговорюсь, что здесь можно еще порассуждать на тему суммы степеней вершин графа). Выберем произвольную вершину, пометим ее А. В ее окружение входит n/2+1 смежных с ней вершин исходного графа. Выберем одну из них, пометим ее В. У нас есть уже две вершины, связанные ребром. Нужно показать, что можно найти третью вершину С, смежную с двумя исходными. Эту третью нужно выбирать из пересечения окружений двух ранее выбранных вершин. Осталось показать, что пересечение это не пусто. В окружение как вершины А, так и вершины В входят по n/2+1 вершины графа порядка n. (n/2+1) + (n/2+1) = n+2 > n. Это значит, у А и В есть как минимум 2 вершины, смежные с ними двумя. Из них и выберем С. 3

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	07.01.2015, 14:32	5
	Тут даже имеет место более сильное утверждение: Каждое ребро входит в треугольник. 3

Треугольник как подграф

Решение