0
$\begingroup$

How would you prove that for a connected graph with an even number of vertices and an odd number of edges, at least one of the vertices has an odd degree?

My first attempt at solving this has been to show that the smallest connected graph with an even number of vertices is a graph with 2 vertices and one edge connecting them. From here, to maintain a connected graph, even number of vertices and an odd number of edges we must add both the vertices and edges by even numbers, and when adding in even numbers the degree of a vertex will not change so it must be odd.

However, this does not seem strong, so could anyone inform me on how to start a proof by contradiction?

I understand the first line of the proof by contradiction would be to assume that every vertex has even degree, but where should I go from there?

Is this not a connected graph with an even number of vertices and an odd number of edges for which an Eulerian tour exists?

$\endgroup$
2
  • 1
    $\begingroup$ Yes, the graph you indicated in your edit is a good example of an Eulerian graph with an even number of vertices and an odd number of edges. $\endgroup$
    – bof
    Nov 19, 2014 at 1:48
  • $\begingroup$ For the question in the first sentence, not the question in the title: assume all the vertices have even degree, use the handshaking lemma, and check divisibility by $4$. $\endgroup$
    – user856
    Nov 21, 2014 at 17:24

1 Answer 1

Reset to default
1
$\begingroup$

The claim you want to prove is false -- you've given a counterexample to it yourself.

So the answer to "How would you prove ..." is: That is impossible to prove, because it is not true.

$\endgroup$

You must log in to answer this question.

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