Buenas estimados, espero que se encuentren bien.
Intente realizar este ejercicio caso a caso pero al fin al cabo se vuelve imposible, por ende me gustaria que me brindasen al menos una idea de por donde tomar este ejercicio.
Saludos.
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