0
$\begingroup$

given a disconnected graph $G$ with 2 components that in one of them all the vertices have even degrees (let's call it $Q$ and the other one $K$), prove that by adding one vertex (call it $s$) to G and edges from the added vertex to the original edeges we can get a simple graph $G'$ that has an eulerian path.

What I did so far:

I've looked at component K (not the one with all the vertices with even degrees):

  • if it has even number of odd-degree vertices let's put an edges between $s$ and every such vertex in $k$ , by doing that we get that all the vertices in $K$ are even-degree and $s$ has also even-degree. now let's put an edge between $s$ and some vertex in component $Q$ -let's call it $f$ - and now we have 2 vetices with odd degree-$s$ and $f$ and now we can say that $G'$ is connected and has an eulerian path.

The problem is the other case - when $K$ has odd number of odd-degree vertices. I don't know what to do in this case because the approach of the first case does not work here.

$\endgroup$
4
  • 1
    $\begingroup$ Hint: is it possible for a graph $K$ to have an odd number of odd-degree vertices? $\endgroup$
    – John Hughes
    May 18, 2018 at 11:25
  • $\begingroup$ oh I forgot this..! thank you $\endgroup$
    – chendoy
    May 18, 2018 at 11:30
  • $\begingroup$ no sute how to do so, do you mean I'll post an answer and will quate your comment in it? $\endgroup$
    – chendoy
    May 18, 2018 at 14:16
  • $\begingroup$ Apologies; I wrote it but forgot to "submit". You can now accept it. $\endgroup$
    – John Hughes
    May 18, 2018 at 14:38

1 Answer 1

Reset to default
1
$\begingroup$

Hint: is it possible for a graph K to have an odd number of odd-degree vertices?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .