Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
How many vertices of odd degree can a graph have? Handshaking lemma –  Martin Sleziak Oct 22 '12 at 17:38
    
This lemma and Michaels answer helped me out! –  Christian Ivicevic Oct 22 '12 at 17:51

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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? –  Christian Ivicevic Oct 22 '12 at 17:41
    
It has an Eulerian cycle iff every vertex has even degree. Paths are less restrictive. –  Michael Biro Oct 22 '12 at 17:43
    
I am sorry, then I have translated it wrong. I have to work with a cycle - editing it now! –  Christian Ivicevic Oct 22 '12 at 17:45
1  
This statement should also work for Eulerian cycles if you use the parity argument for vertices of odd degree. See Martin Sleziak's comment. –  Michael Biro Oct 22 '12 at 17:46
    
The handshaking lemma and your edit gave me a good clue to solve this. Thanks! –  Christian Ivicevic Oct 22 '12 at 17:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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