1
$\begingroup$

What are all the tricks that make a graph drawable? I know that a graph is drawable when you can draw the graph without lifting your pen off the paper and without retracing any edges. I know that if every vertex has even degree then it is Eulerian. I know that Eulerian graphs can have repeated vertices.

1) Can you ever have a connected graph with an odd number of vertices each with an odd degree? I've tried a lot of connected graphs and it looks like the answer is no.

2) Will a graph that is Eulerian always start and end on vertices of odd degree if the graph contains vertices of odd degree? Looks like it so far with all the Eulerian graphs I've constructed so far.

3) What are all the tricks for finding if a graph is Eulerian?

$\endgroup$
2
  • $\begingroup$ For your 1) the answer is no. The reason is that $\sum\limits_{v\in V}d(v)=2\cdot |E|$. The RHS is even, while the LHS is a sum consisting of an odd number of odd numbers. $\endgroup$
    – DKal
    Mar 18, 2014 at 7:45
  • $\begingroup$ 1) Being connected implies what about degree? What determines degree? How much is degree increased by? Edit: That was a hint to Adam. Dkal beat me to it. $\endgroup$
    – Display Name
    Mar 18, 2014 at 7:47

1 Answer 1

Reset to default
3
$\begingroup$

1.) This is impossible. It is known as The Handshaking Lemma. If you add up the degrees of each vertex of a graph, you end up counting each edge exactly twice, thus $$ \sum_{v\in V(G)}\deg(v)=2e $$ where $e$ is the number of edges in your graph. Now suppose you had a graph with an odd number of vertices with odd degree, when you add up all your degrees, you would cause your sum to be odd. But adding up the degrees counts the edges twice, which is even. A contradiction!

2.) A graph that has an Eulerian $path$ can have exactly 2 vertices of odd degree and the path must start at one odd vertex and end at the other. A graph that has an Eulerian $circuit$ has all vertices of even degree. The circuit must start and end at the same vertex.

3.) A graph is Eulerian if and only if every vertex of even degree.

$\endgroup$

You must log in to answer this question.

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