Дискретная математика, графы

1а. 6 вершин (0²; 1; 2; 3; 4; 5), одна инцидентна двум рёбрам, а остальные - по одному ребру каждая.
Если мы рассмотрим связный граф

 1 ─ 0 ─ 2 

то степени его вершин 0, 1, 2 будут такими, как в условии. При этом мы не можем добавить в него ни одной вершины, не нарушив степеней вершин 0, 1 или 2. Значит, связных графов для данной последовательности не существует.
Вообще, тут даже проще применить лемму о рукопожатиях: в любом графе (даже несвязном) сумма степеней вершин - чётное число, а в данной последовательности она равна 7.

1б. 4 вершины (1²; 2³; 3²; 6) соответствуют, например, таком графу:

 1 ─ 2 ─ 6

│   │

└── 3 

1в. По лемме о рукопожатиях, данная последовательность не соответствует никакому графу, т.к. сумма степеней вершин (9) - нечётное число.

2а. Мы построили только один граф (1б). Радиус графа = 1.

2б. Остовные подграфы графа 1б (список не исчерпывающий, конечно):

 1 ─ 2 ─ 6

    │

    3



1 ─ 2 ─ 6

│

└── 3 

Примеры порождённых подграфов того же графа:

 1 ─ 2

│   │

└── 3



1 ─ 2 ─ 6 

Пример подграфа, не являющегося ни остовным, ни порождённым (множество вершин не совпадает, и включены не все рёбра, соединяющие вершины исходного графа):

 1 ─ 2

│

└── 3 

2д. Матрица расстояний графа 1б:

 0  1  1  2

1  0  1  1

1  1  0  2

2  1  2  0 

Матрица смежности:

 0  1  1  0

1  0  1  1

1  1  0  0

0  1  0  0 

(получается из матрицы расстояний заменой всех элементов, больших единицы, на 0, т.к. такие расстояния могут возникнуть только у несмежных вершин)

2е. В графе 1б есть Эйлеров путь (проходящий все вершины по одному разу: 6-2-1-3 или 6-2-3-1), но отсутствует Эйлеров цикл (такой путь не является замкнутым). Поэтому граф не является эйлеровым.

3.. При n > 4, например, это - граф "колесо" (погуглите, что это такое, и быстро найдёте примеры с картинками). От центра до любой вершины - одно ребро, а для каждой вершины "обода" обязательно найдётся другая вершина "обода", до которой более одного ребра. Можно убрать "обод" колеса, тогда и при n = 3 и n = 4 можно построить такие графы.
При n = 4:

 1 ─ 2 ─ 6

    │

    3 

При n = 3:

 1 ─ 2 ─ 3 

При n = 2 обе вершины связного графа будут его центром.