Hola Manuel.
Puede ser útil pensarlo en un caso particular, como n = 5 o 6 para poder dibujarlo concretamente. Te recomiendo que primero dibujes 2 de los nodos separados del resto, y dibujes una línea de corte que divida al plano en dos regiones, una que contenga a esos 2 nodos y la otra al resto. Las aristas que son atravezadas por esa línea son las que tenés que sacar. Después hay que verificar que separar más de 2 nodos resulta en una cantidad mayor de aristas que de esta forma. Una vez que hayas hecho eso, es un problema de conteo fácil determinar cuántas aristas son.
Saludos,
Gabriel