2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Разбиение вершин графа на два подмножества
Сообщение09.05.2021, 10:09 


15/04/20
201
Дан граф с кол-вом вершин $n, n \geqslant 6$. Известно, что $\deg(v)=3, \; \forall  v \in V$, $V$ - множество вершин графа. Докажите, что вершины графа можно разбить на два непустых подмножества так, что в каждом подмножестве любая вершина соединена ребром как минимум с двумя другими вершинами из этого же подмножества.

Всё, что удалось вытянуть из условия: из того, что степени каждой вершины равна $3$ следует, что в графе есть цикл(в любой компоненте связности нет висячей вершины), а так же то, что подмножества из разбиения одновременно содержат чётное или нечётное число вершин (поскольку $\left\lvert E \right\rvert = \frac{3}{2}n$).

Я попытался строить эти подмножества итеративно, однако не хватило строгости рассуждений. Попробовал от противного, но запутался окончательно.

 Профиль  
                  
 
 Re: Разбиение вершин графа на два подмножества
Сообщение11.05.2021, 12:50 
Заслуженный участник
Аватара пользователя


18/05/06
13435
с Территории
Вот, допустим, граф $K_{3,3}$. Как его разбить?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Vladimir Pliassov


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group