# Is it possible to make a graph eulerian by adding exactly one node?

Let $$G=(V,E)$$ denote a connected graph with $$|V|\geq 2$$. Is it possible to add a new node $$v$$ with corresponding edges $$e_k=\{v,w\}$$ with $$w\in V$$(*1) such that $$(V\cup\{v\},E^\prime)$$ contains an eulerian cycle where $$E^\prime=E\cup\left(\bigcup\{e_k\}\right)$$? Prove if possible; otherwise, show a counterexample.

(*1) It is not mandatory to connect the new node $$v$$ to every other node. One is allowed to omit some of them.

Thoughts. Basically I think it is possible, however I don't know exactly how to argument. I was thinking about comparing the degrees of all nodes and when adding new edges connecting the new node to the old graph to argument when degrees get even/odd to show, that in the end it is possible that all nodes will have even degree, no matter which graph we had at the beginning. This is the result I got when adding one edge and inspecting that there can't be a circle, and obviously the degree of the new node is 1. That way I would have to add an even number of edges to achieve what has to be done.

Question. Can anyone give me some hints on how to start and what exactly to prove?

• How many vertices of odd degree can a graph have? Handshaking lemma Oct 22 '12 at 17:38
• This lemma and Michaels answer helped me out! Oct 22 '12 at 17:51

Then look at the number of odd degree vertices in $G$, and figure out the correct edges to use to make $(V \cup \{v\},E^\prime)$ have at most two vertices with odd degree.
Edit: If you want an Euler cycle, then you must make $(V \cup \{v\},E^\prime)$ have no vertices of odd degree. We'd then want to connect the new vertex to every odd degree vertex in $G$ and then argue that the new vertex has even degree.