Помогите пожалуйста! комбинаторика

Question

Помогите пожалуйста! комбинаторика

elendavi Ученик (62), открыт 2 часа назад

Связный граф подвесили за вершину A. Оказалось, что внутри получившихся уровней нет рёбер. Выберите все гарантированно верные утверждения.

Исходный граф — цикл.

Исходный граф — дерево.

Исходный граф двудольный.

Если у вершины, отличной от A, степень k, то она соединена ровно с k−1 вершиной следующего уровня.

Если у вершины, отличной от A, степень k, то она соединена ровно с k вершинами следующего уровня.

В графе нет циклов длины 3 .

В графе нет циклов длины 4.

В графе нет циклов длины 5.

Answer 1

Верными являются следующие утверждения:

Исходный граф — дерево. Если бы в исходном графе были циклы, то после подвешивания за вершину A внутри уровней появились бы рёбра. В дереве нет циклов.

Если у вершины, отличной от A, степень k, то она соединена ровно с k−1 вершинами следующего уровня. Это следует из того, что одна из k дуг идет к предыдущему уровню (к вершине, от которой граф подвешен), а остальные k-1 дуг идут к вершинам следующего уровня.

Остальные утверждения неверны:

Исходный граф — цикл. Цикл не является деревом.

Исходный граф двудольный. Граф может быть не двудольным.

Если у вершины, отличной от A, степень k, то она соединена ровно с k вершинами следующего уровня. Неверно, так как одна ветвь идет к вышестоящей вершине.

В графе нет циклов длины 3, 4, 5. Граф может содержать циклы большей длины, которые не повлияют на условие задачи.

Таким образом, только два утверждения гарантированно верны.