1. Что называется степенью вершины?

Степень вершины графа — это количество рёбер, инцидентных этой вершине. В петлю, если она есть, обычно засчитывают дважды.