when i was checking it manually i checked for 4 and 6 and just naively concluded there must be for others but u R right , 3 and 5 so far do not have the solution |N|-1!

             e
+-----------------------+
|        b              |
+-----------------+     |
|      d          |     |
+-----------+     |     |
|  a     b  |  e  |  a  |
1-----2-----3-----4-----5
      |     |     c     |
      |     +-----------+
      |        d        |
      +-----------------+
      
      |     c     |
      +-----------+
[download]

PS this is definitely a solution but as u said for larger graphs it takes forever.
Thnx!