If you restrict the vertices you are looking at to the ones within some fixed distance from a central vertex, there are only finitely many cases. This could make brute-forcing possible. (I do agree, though, that this is non-trivial and it looks like that was mainly what you were getting at).