Дуги а = (хi, хj), хi ≠ хj, имеющие общие концевые вершины, называются смежными. Две вершины хi и хj называются смежными, если какая-нибудь из двух дуг (хi, хj) и (хj, хi) или обе одновременно присутствуют в графе.
Если вершины x и y неориентированного графа G соединены ребром (x,y), то вершины называются смежными, в противном случае - несмежные.
Для неориентированного графа G: вершины, смежные вершине s - это x и y; смежные вершине x - это s,y,z; смежные вершине z - это x,y; смежные вершине y - это s,x,z.
Степень вершины определим как число ребер, инцидентных ей. Вершину нулевой степени будем называть изолированной (например, вершина v5 на рис. 1.1, а). Для вершин орграфа определяются полустепени захода (число заходящих в вершину дуг) и исхода (число выходящих дуг). Степень вершины определяется как сумма полустепеней захода и исхода