It would be interesting to solve such a problem on an arbitrary graph (not a tree) or to say that there is no solution for such a graph.

it is well known problem. but its hard to implement. You should find a clique of size 5 or complete bipartite subgraph with size (3, 3). There is no solution if and only if there exist such subgraph or topologicaly equal to that(other vertex can adjust 2 dif. vertexes of such subgraph). I took lectures about that a long time ago. Can't find source now.

Edited by author 26.05.2024 21:22