A graph puzzle

[reiniscirpons]

This is not meant for the Wednesday meeting discussion, I just thought I'd put something here for entertainment.

A graph is simple if it is undirected and does not have multiple edges or loops. Call a simple graph $G$ könish if it can be drawn on a piece of paper without lifting up the pen, so that no two edges of the graph cross, and no edge of the graph is drawn twice.

So, for example the following graph on the right is könish, the order in which to draw it in a single stroke without crossing edges is given on the left:

The following graphs is not könish, as there is no way to draw it without drawing an edge twice:

And another example of a non-könish graph, there is no way to draw it without edges crossing:

For every $n\geq 2$ let $ö(n)$ be the largest number of edges of any könish graph with $n$ vertices. Since $K_3$, the complete graph on $3$ vertices, is könish, $ö(3) = 3$. But already for $n=4$ we can shown that $K_4$ is not könish (why?), so that $ö(4) < 6$. In fact, $ö(4) = 5$.

Question: Can we (using gap and the digraphs package, or otherwise) determine:

1. The number $ö(5)$ and all the könish graphs attaining it? I.e. all the $5$-vertex könish graphs with $ö(5)$ edges.
2. The number $ö(6)$ and all the könish graphs attaining it?
3. Whats the largest number $n$ for which we can reasonably compute $ö(n)$ via the digraphs package?
4. If there is there a formula for $ö(n)$? If not, can we approximate the growth of it?
5. If it is possible to describe all könish graphs with $n$ vertices whose number of edges equals $ö(n)$? Is there an algorithm which enumerates them?