Неравенство все же Вы имели в виду в другую сторону, так?
Ну как бы каждому помеченному графу на

вершинах с

ребрами отвечают как минимум

помеченных на

вершине с

ребрами -- тот, где

-я вершина соединена с 1, тот, где

-я вершина соединена с 2... Так?
То есть даже так, что ли:

.