2
$\begingroup$

This is a homework question. However, I don't think that such a graph exists. Here's my attempt at proving that (I know I'm wrong; please tell me where I went wrong!):

For contradiction, assume such a graph G exists. Assume the vertices are called a, b, c, d, and e. Since the addition of any edge produces an Eulerian graph, adding the edge ab would do so. In order for a graph to be Eulerian, all its vertices must be of even degree. So now a, b, c, d, and e are of even degree. But that meant that beforehand, a and b were of odd degree, since adding one edge between two vertices changes their parity. So G has vertices a and b of odd degree, and c, d, and e of even degree. (*)

Since the addition of any edge produces an Eulerian graph, adding the edge cd would also do so. In order for a graph to be Eulerian, all its vertices must be of even degree. So now a, b, c, d, and e are of even degree. But that meant that beforehand, c and d were of odd degree, since adding one edge between two vertices changes their parity. So G has vertices c and d of odd degree, and a, b, and e of even degree. (**)

So (*) and (**) make a contradiction!

Where am I going wrong in this proof? I know I must be wrong because I have to find an example of such a graph (you could be finicky and say that some the vertices could be of degree 0, but it's still going to be a problem)

$\endgroup$
8
  • 2
    $\begingroup$ You can't assume that you can add an edge between two specific vertices like $a$ and $b$ because an edge may already exist between $a$ and $b$. $\endgroup$
    – John Douma
    Mar 8, 2019 at 17:20
  • $\begingroup$ @JohnDouma Under your interpretation, there are at least two such graphs: $K_5 - e$ for any edge $e$ (because the only edge we can add is the missing edge $e$, getting the Eulerian graph $K_5$) and $K_5$ itself (because we can't add any edges, so the statement holds vacuously). $\endgroup$
    – Misha Lavrov
    Mar 8, 2019 at 17:47
  • $\begingroup$ @MishaLavrov I thought we were working with graphs, not multigraphs. $\endgroup$
    – John Douma
    Mar 8, 2019 at 17:53
  • $\begingroup$ ohh I see so multigraphs aren't allowed. That makes way more sense $\endgroup$
    – dora
    Mar 8, 2019 at 17:55
  • $\begingroup$ @dora You posted the problem. Are you allowed to use multigraphs? $\endgroup$
    – John Douma
    Mar 8, 2019 at 17:59

1 Answer 1

Reset to default
2
$\begingroup$

The intended answer is probably $K_5 - e$: the complete graph of order $5$, with a single edge removed. The only way to add an edge to this graph is to add the unique missing edge, which results in the Eulerian graph $K_5$.

There are two quibbles with this:

  • If we consider multigraphs, rather than simple graphs, we could add an edge that's already present. In that case, it's possible to add a new copy of an existing edge to $K_5 - e$, and create a non-Eulerian multigraph. When considering multigraphs, the body of the question is a proof that there can be no solution.
  • If we consider simple graphs only, so we specifically rephrase the property as "the addition of any edge not already present in the graph produces an Eulerian graph", then there is a second solution: the newly-rephrased property is vacuously true of $K_5$ itself, because there is no possible edge we can add.

I imagine that the question was intended to be about simple graphs only, and the vacuously-true answer of $K_5$ was overlooked by the author of the problem.

(This is an old question that mostly got resolved in the comments; I'm providing an answer for completeness.)

$\endgroup$

You must log in to answer this question.

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