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?

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

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.

  • $\begingroup$ I know that a connected graph has an Eulerian path iff all vertices have even degree. I even proved that yesterday, isn't that contradicting with your mentioned property? $\endgroup$ Oct 22 '12 at 17:41
  • $\begingroup$ It has an Eulerian cycle iff every vertex has even degree. Paths are less restrictive. $\endgroup$ Oct 22 '12 at 17:43
  • $\begingroup$ I am sorry, then I have translated it wrong. I have to work with a cycle - editing it now! $\endgroup$ Oct 22 '12 at 17:45
  • 1
    $\begingroup$ This statement should also work for Eulerian cycles if you use the parity argument for vertices of odd degree. See Martin Sleziak's comment. $\endgroup$ Oct 22 '12 at 17:46
  • $\begingroup$ The handshaking lemma and your edit gave me a good clue to solve this. Thanks! $\endgroup$ Oct 22 '12 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.