дискретная математика. задача Опции

[Николай]

Помогите пожалуйста.
1.При каких n существуют графы с n вершинами, каждая их которых имеет степень 3? степень 4?.
2.Перчислить все попарно неизоморфные ориентированные графы без петель с 3-мя вершинами и 3-мя ребрами.

[Гость]

3.Определить число ребер в:
полном графе с n вершинами,вкотором 2 любые вершины смежны(Kn);
полном двудольном графе(Kn,q).
4.Найти радиус и диаметр каждого из графов:
полном графе с n вершинами,вкотором 2 любые вершины смежны(Kn);
полном двудольном графе(Kn,q);
и еще какое то Сn.

[Гость]

Ну блин что никто не знает ?

[Atos]

1. Это полные графы K4 и K5 соответственно.

2. Таких графов всего два. Подумай и нарисуй сам

3.
a) (n-1)*n/2
б) n*q/2

4. Для всех этих графов радиус равен диаметру
a) r=d=1
б) r=d=2
в) r=d=целая часть(n/2)

[Гость]

Уважаемый Atos, Вы не можете нарисовать графы к 4-му заданию?
Обьясните почему 2 графа а не 4 во 2-м задании?
В третем задании это делаеться по формулам?

[Atos]

Обьясните почему 2 графа а не 4 во 2-м задании?

Вот 2 графа. Откудa взяться ещё двум?

В третем задании это делаеться по формулам?

Эти формулы выводятся из общих соображений. В Kn каждая из n вершин соединена с n-1 остальными. каждое ребро соединяет 2 вершины, поэтому делим на 2. Вот со второй формулой я немного ошибся, извиняюсь... В K(n,q) каждая из n вершин соединена с q противоположными, и тут делить на два не надо было... просто n*q.

Вы не можете нарисовать графы к 4-му заданию?

Полный граф - каждая вершина соединена с каждой. полный двудольный - вершины разбиты на два множества, и каждая вершина соединена со всеми из противоположного множества. Cn - это простой n-вершинный цикл (замкнутая цепочка). Разве нет учебника с рисунками?

[Лена]

помогите доказать:
Докажите, что в любом графе есть либо три попарно смежные, либо три попарно несмежные вершины
За ранее спасибо!!!

[Michael_Rybak]

Этого нельзя доказать. Это недоказуемо.

[мисс_граффити]

...зато легко доказать обратное.
если в графе всего две вершины...