Диаметр Connected подграфа со всеми узлами

Question

лемму 1: Если Н подграф графа G, то dist_G (U, V) < = dist_H (U, V).

Доказательство Каждый путь уф в H появляется также в G и G могут иметь дополнительные пути уф, которые короче, чем любой путь УФ в H.

Лемма 2: Если H подключен подграфа графа G, таким образом, что V (H) = V (G), то диаметр (G), ≤diameter (Н)

Доказательство

1. диаметр (G) = max {dist_G (u, v)} для всех u, v в V (G)
2. Предположим, что диаметр (G) = dist_G (x, y) для некоторых x, y в V (G) = V (H)
3. диаметр (Н) = dist_H (а, б) для некоторого а, б, в V (H) = V (G)
4. Заметим, что dist_H (с, т) < = dist_H (а, б) для всех S, T в V (Н)
5. dist_G (х, у) < = dist_H (х, у) для леммы 1
6. dist_H (х, у) < = dist_H (а, б) для (4)
7. Поэтому диаметр (G) < = диаметр (H)

Нетрудно видеть, если мы заменим H для любого подграфа, то лемма не выполняется. Итак, мой вопрос заключается в предыдущем доказательстве, когда я использую связь H.

Answer 1

По определению диаметр графика определен только для подключенного графика (в противном случае невозможно вычислить минимальное расстояние между двумя точками, которые не связаны).