Решить задачи

Здравствуйте!

1. Существует ли такой граф на 10 вершинах, в котором 37 рёбер и есть висячая вершина?

2. Доказать, что в матрице смежности графа количество строк с нечетным числом единиц чётно.

3. Сколько рёбер в регулярном графе типа (n,k)? Докажите, что такой граф существует, если и только если k<=n-1 и nk четно.

4. Докажите, что в неориентированном графе существуют, по крайней мере, две вершины, степени которых равны. Верно ли аналогичное утверждение для ориентированного графа? Степени вершин равны, если равны обе полустепени.

5. Докажите, что для любого n существует граф, у которого равны степени только двух вершин.