97. В дереве 1001 вершина. Может ли быть так, что: а) длина любой цепи в этом дереве не больше 1; б) длина любой цепи в этом дереве не больше 2; в) в этом дереве найдётся цепь длиной 1000?

а) Нет. В дереве с 1001 вершиной имеются рёбра, поэтому цепь длины 1 существует, но условие «любой цепи не больше 1» возможно только для звезды; однако в звезде есть цепь длины 2. Значит, такое дерево невозможно.

б) Да. Можно взять дерево-звезду: центральная вершина соединена с 1000 концевыми вершинами. Любая цепь имеет длину не более 2.

в) Да. Можно взять цепь из 1001 вершины. Расстояние между её крайними вершинами равно \(1000\).

Ответ: а) нет; б) да; в) да.