2
$\begingroup$

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?

  • 0
    This lemma and Michaels answer helped me out!2012-10-22

1 Answers 1

3

Use the property: A connected graph has an Eulerian path if and only if it has at most two vertices with odd degree.

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.

  • 0
    The handshaking lemma and your edit gave me a good clue to solve this. Thanks!2012-10-22