Такой вопрос назрел. Дан граф. Требуется покрыть все ребра графа минимальным количеством клик.(ВАЖНО: каждое ребро РОВНО в одной клике). Например: Граф из ребер (1, 2), (1, 3), (2, 3), (3, 4), (2, 4) Ответ 3.

Пытался гуглить, ничего не нашел путного. Если кто может пруфануть класс сложности, буду благодарен.