Thread: Eulerian graph with even vertices and odd edges

Hi guys, i've been set a problem which is to either illustrate a graph which is Eulerian with even vertices and odd edges; or show why no such graph can exist?

Intuitively im thinking the latter is true, but im struggling to find a sound explanation as to why this is the case. Any help will be appreciated!! thanks a million.

Originally Posted by euler786

Which is Eulerian with even vertices and odd edges; or show why no such graph can exist?

There is a real problem with definitions here. Textbooks and authors do not always agree on the definition of Eulerian Graphs.

It seems that most current texts agree that an Eulerian graph is one in which there is a closed walk, no edge can be repeated. In this case show that all vertices are even.

On the other hand, we can find older texts that talk about traceable graphs being Eulerian. That is, there is a walk( not necessarily closed) that includes each edge exactly once. In this case, there are at most two odd vertices.

So check your text material for the definition in use.

A graph is Eulerian if it contains an Euler Tour, an Euler Tour contains a tour where each edge is traversed exactly once, a tour is a closed edge sequence (walk) where each edge is traversed at least once.

A graph is semi-Eulerian if it contains an Euler Chain, an Euler Chain contains a chain where each edge is traversed exactly once, a chain is an edge sequence (walk) where each edge is distinct.

A graph is Eulerian if every vertex has even degree. A graph is semi-Eulerian if it contains at most two vertices of odd degree.

These are the defintions and tests available at my disposal.

I know intuitively that there can be no graph with an even number of vertices and an odd number of edges and still be Eulerian; but i can't even begin to start a sound argument.

Thanks for replying Plato

Originally Posted by euler786

I know intuitively that there can be no graph with an even number of vertices and an odd number of edges and still be Eulerian; but i can't even begin to start a sound argument.

It is not if the number of vertices or edges is even or odd! It is about the degree sequence of the vertices in a connected graph.

If all the vertices are of even degree (each vertex is concurrent with an even number of edges) then the graph is traceable with a closed path including each edge exactly once. You see that any vertex can be repeated. Thinking a bit more, we realize that if we ‘enter’ a vertex and ‘leave’ it on our walk then the vertex must be even. Moreover, we must begin and end at the same vertex.

If the connected graph has exactly two odd vertices we can trace it using each edge exactly once. But we must begin at one of the odd vertices and end at the other (again using the in-out reasoning). So that walk cannot be closed.

lol, ok im a bit confused here; the question is;

'draw a Eulerian graph with an even number of vertices and an odd number of edges; or explain why such a graph can't exist?'

does that help with any confusion...? i dont think its asking about the degree of the sequences its asking for a total even vertices with a total odd edges...? im not sure now!!

Right yes i get you now, thanks for the help mate, have u done this one before..? im finding proofs quite hard, i can a follow a proof and understand it well enough, but i struggle to produce my own, does it just come to you? what do you reckon could help improve this side of my maths...? and once again, thanks for the help, i really do appreciate it.
gtg bye for now

This may be what you are looking for.
I reread your definitions.