Для каждой вершины существует не более чем $$$O(\sqrt{m})$$$ соседей большей степени.

Почему? Потому что если у вершины степень не более чем $$$O(\sqrt{m})$$$, у нее самой существует не более $$$O(\sqrt{m})$$$ соседей. Если же у вершины степень больше корня, то существует не больше чем $$$O(\frac{m}{\sqrt{m}})$$$ вершин степени больше корня, что есть $$$O(\sqrt{m})$$$.

Таким образом, можно решать задачу следующим образом:

Зафиксируем вершину $$$v$$$ степени три в алмазе, запомним в массиве вершины, которы являются ее соседями. Затем переберем соседа $$$u$$$ этой вершины и соседа вершины $$$u$$$, но у которого степень больше (при равенстве степеней можно сравнивать по номеру). Если этот сосед соединен с $$$v$$$ (что вы проверяете за $$$O(1)$$$, так как вы запомнили в массив), то прибавим к степени вершины $$$u$$$ и степени этого соседа единицу.

Таким образом, для всех соседей вершины $$$v$$$ мы нашли, сколько у них есть соседей, которые также являются соседями вершины $$$v$$$. Не трудно заметить, что количество алмазов, в которых вершина $$$v$$$ имеет степень три равно $$$\sum{\frac{deg_v(deg_v -1)}{2}}$$$.

В конце каждый алмаз мы посчитали два раза, поэтому нужно поделить ответ на два.

Время работы $$$O(m\sqrt{m})$$$ и $$$O(m)$$$ памяти.