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$
  • 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 '14 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$ – Rahul Nov 21 '14 at 17:24
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$

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.