Коля решил нарисовать граф из 100 вершин, в котором проведены все ребра. Ему оставалось нарисовать 98 ребер, когда ручка перестала писать. Коля не глядя сказал, что на доске нарисован связный граф. Мог ли он ошибаться?
В полном графе из 100 вершин из каждой вершины выходит по 99 ребер к остальным. Предположим, что в графе, нарисованном Колей, есть изолированная вершина. Тогда до полного этому графу будет не хватать по крайней мере тех самых 99 ребер. Но Коля не успел провести только 98 ребер, а значит, наше предположение ложное. Каждая вершина графа соединена хотя бы с одной другой вершиной, то есть он точно является связным.
не мог
Пошаговое объяснение:
В полном графе из 100 вершин из каждой вершины выходит по 99 ребер к остальным. Предположим, что в графе, нарисованном Колей, есть изолированная вершина. Тогда до полного этому графу будет не хватать по крайней мере тех самых 99 ребер. Но Коля не успел провести только 98 ребер, а значит, наше предположение ложное. Каждая вершина графа соединена хотя бы с одной другой вершиной, то есть он точно является связным.