Euler's solution for the bridges of Königsberg problem

This links back to the earlier blog post: The bridges of Königsberg

From the diagram it seems like this may be possible. However, after a few attempts using trial and error of different routes you keep ending up having to use an edge more than once.

Graph theory allows the problem to be simplified down to:

The famous mathematician Leonhard Euler came up with necessary and sufficient conditions for a graph to be Eulerian: starting at any vertex you can cross every edge and end up back where you started
(Or, equivalently, the graph can be drawn without having to take the pen off the paper)

Or semi-Eulerian: starting at one vertex you can walk along every edge but end in a different place to where you started.

For a graph to be Eulerian every vertex must have even degree (the number of edges coming out of that vertex).

Using the simplified graph version of the bridges of Königsberg problem we can see that degrees of the vertices are:

a 3

b 5

c 3

d 3

So it is clearly not possible to walk across every edge (bridge) exactly once beginning and ending in the same place or different places.

A natural question is to ask how many edges need to be added to make the graph Eulerian?

Hint: every edge must start and finish at a vertex