Определение. Если {а, b} – неориентированное ребро, тогда вершины а и b называются концами или концевыми вершинами ребра {а, b}. Ребро {а, b} называют также инцидентным вершинам а и b. Обратно, говорят, что вершины а и b инцидентны к ребру {а, b}. Пример 1. В неориентированном графе G1 (см. рис. ниже) вершина а инцидентна рёбрам{a, c} и {a, b}, вершина b инцидентна двум рёбрам {a, b} и{b, d}, вершина с инцидентна трём рёбрам {a, c}, {c, d} и {c, е}, вершина d инцидентна трём рёбрам {b, d}, {c, d} и {d, f}, вершина e инцидентна ребру {c, e}, вершина f инцидентна ребру {d, f}...

Одноклассники Андрей, Богдан, Вадим, Григорий, Дмитрий и Евгений устрои­ли турнир по настольному теннису и решили играть каждый с каждым. Турнир ещё не за­кончен. Рёбра графа показывают, кто с кем сыграл к этому моменту. Больше всех партий сыграли Евгений и Григорий — по три партии. Вадим пока не сыграл ни одной партии, а Андрей, Богдан и Дмитрий сыграли по две. Можно сказать, что в графе степень вершины В равна 0, степени вершин А, Б, Д равны 2, а степени вершин Г и Е равны 3. Степенью или валентностью вершины в графе называется количество исходящих из неё рёбер...