Commons license.

Your support will help MIT OpenCourseWare

continue to offer high quality educational resources for free.

To make a donation or view additional materials

from hundreds of MIT courses, visit MIT OpenCourseWare

at ocw.mit.edu.

PROFESSOR: So today we're going to continue

our course on the graph theory.

It's going to be a mixture of all kinds of topics.

We first start off with Euler tour,

and then we get into directed graphs

and cover the definitions.

And we'll talk about a special type, which

are called tournament graphs.

And we'll do a whole bunch of proofs,

and hopefully you will all contribute to make this work

and think about how to do this.

So next week we will continue with graph theory,

and we will discuss a very special type.

We will use directed graphs in communication networks.

And on Thursday, we'll actually use these special types

of graphs that we'll talk about in a moment, DAGs.

So let's talk about Euler tour.

Euler, a famous mathematician, he asked the question

like-- he lived in Konigsberg.

And there were seven bridges.

He was wondering, can you traverse all the bridges

exactly once.

So he would start walking and try to cross all those bridges.

And apparently this little islands in sort of the river

as well, and so on.

So how can you do that?

This is actually the birth of graph theory.

And this particular problem is named after him.

So what is an Euler tour?

It's actually defined as a special walk.

It's a walk that traverses every edge exactly once.

So it turns out the you can actually characterize

these types of graphs.

So we are talking here about undirected graph,

so continuation of last time.

So the edges that we consider have no direction.

We'll come back to that in a moment.

We will start defining those later.

So Euler tour is a walk that traverses every edge exactly

once.

And at the same time, it's also a tour.

So that means that it actually starts and finishes

at the same vertex.

Now it turns out that undirected graphs,

the graphs that we've been talking about,

those that Euler tours can be easily characterized.

And that's the theorem that we're going to prove next.

The theorem states that actually,

if a connected graph has an Euler tour,

if and only if, every vertex of the graph has even degree.

So that's a very nice and simple and straightforward

characterization.

So how can we prove this?

So let's have a look.

So first of all, we have an if and only if statement.

So we need to prove two directions.

We need to proof that if I have a connected graph that

has an Euler tour, I need to show that every vertex has

even degree.

And also the reverse-- if I have a graph for which every vertex

has even degree, I need to show that it has an Euler tour.

So the proof consists of two parts.

So let's first do this implication,

where we assure that we have connected

graph that has an Euler tour.

So assume we have a graph.

So we have G with the vertex at V, edge is at E,

and it has an Euler tour.

So what does it mean?

Well, it's really means that we can walk

from some start vertex, V0.

We can go all the way around to V1, and some more, and so on,

to V, say, k minus 1.

And then end vertex is the same as the start vertex.

So we have a walk that goes all around the whole graph.

So every edge in this walk are exactly the edges

that are in the graph.

And each edge in the graph is offered exactly once.

So what does it mean?

So let's write this down actually.

So since every edge is traversed once-- every edge in E

is traversed once-- what can we conclude from that?

Can we say something about, given such as walk of length k,

what can we say about the number of edges, for example?

What can we say about the degree of the vertices?

Because that's what you want to show, right?

You want to show that every vertex has even degree.

Does anyone know how to go ahead here?

So we know that every single edge in E

is referred ones within this whole walk.

So what kind of properties can we derive?

AUDIENCE: [INAUDIBLE]

PROFESSOR: That's true.

AUDIENCE: [INAUDIBLE]

PROFESSOR: Maybe someone else can pick up here.

So every vertex that I have here, I will enter it.

But I also leave it.

So if I see a vertex in here, I can

see at least two contributing edges

that are coming from this.

AUDIENCE: Then you know that that note has at least

degree 2, but it can't be more than 2

because otherwise that would be the endpoint.

PROFESSOR: Ah.

But is it true though that-- so for example,

this particular note here may repeat itself somewhere else.

I only have a condition on the Euler tour

that every edge occurs exactly ones.

So how could I formally sort of continue to prove?

AUDIENCE: Well, it will intersect itself again,

and you'll leave again and it will still

have the even number.

PROFESSOR: Yeah.

That's true.

That's right.

Any other additions?

AUDIENCE: You can define the number of edges

that it will test by how many you enter it,

so the number of edges that it has

is twice the number of [INAUDIBLE].

PROFESSOR: Yeah.

That's correct. [INAUDIBLE]

AUDIENCE: [INAUDIBLE] traverse once, then every time you enter

a node you have to leave it.

So you can say that you're never going

to leave a node for a node that it already left for from there.

And you're never going to enter from a node you already entered

from or left to from there.

So that's how you can say that you're only going

to increment your degree by 2.

PROFESSOR: That's true.

So what he's essentially saying is

that every edge as I start to count

here, in this particular tour, well they're all different.

So they all counts towards a degree of the node.

So everything that you have been saying is right on.

What we can conclude here is that if you look at a vertex,

say vertex U-- for example, somewhere over here-- well,

it may repeat itself over here.

And it has an incoming and outgoing edge, incoming

and outgoing edge.

And I may have it somewhere else,

but say it's just at those two.

Well, I know that all the edges are different.

So I can clearly count this now.

I can say that the degree of U must

be equal to the number of times that U actually

appears in this tour.

So in the tour from V0 all the way to Vk minus 1.

And then I have to multiply times 2.

And what I said, it's exactly what you have been saying,

all the edges occur exactly once of the whole graph.

So I just count the number of times I see U in here.

I come the number of edges that go into it and leave from it.

Well, that's twice times the number of times

that U actually appears in this tour.

So this implication is pretty straightforward

because now we actually note that the degree of U is even.

So that's great.

So let's talk about the other implication

and see whether we can find a trick to make that happen.

So what do we need to start off with?

Well, now we have to assume that every vertex has even degree.

So let's write this down.

So say we have the graph.

And for this graph we actually issue

that the degree of every vertex V is even.

Well, what can we do?

Well, this is sort of creative trick,

so let me just continue here.

So what we have is if you start to consider a walk, W,

that touches, say, a lot of vertices in such a way

that W is actually the longest walk.

So that's often what you do in graph theory.

You think about, say, the shortest path

or whatever with a certain property, or the longest walk,

or whatever with a certain property.

So that's what you're doing here.

So let W be the longest walk.

And well, we want to prove something about an Euler tour.

An Euler tour has a very specific property

that all the edges occur only once.

So it makes sense to look at walks

in which all the edges of which it walks are unique,

are occurring only once.

So we're interested in the longest walk that traverses

no edge more than once.

So that's important.

Now, let's think about this a little bit.

So the first property that you may want to consider it-- you

really want to show that W is going to be an Euler tour.

That's what we're going to try to prove here.

So the first thing we may want to show

is that actually it goes all around.

So V0 is equal to Vk.

That will be great if we can do this.

So we want to show that this is true.

So what would happen if this would not be the case?

So suppose these two would not be equal to one another.

Well, actually, I'm skipping a little bit ahead here

in the proof, I notice.

So this will be the conclusion of another observation.

So let me start with the first observation.

So first of all, let us consider this end node over

here, this end vertex, Vk.

Now if there is an edge that is not covered in this walk--

and I can lengthen the walk, right?

So if I have, say, another edge, which

looks like Vk, an edge from Vk to some U, where

this edge is not in the walk.

Or the other one is not in the walk.

Well, it doesn't matter in an indirect graph, of course.

So if this is not in the walk, then what can I do?

I can just lengthen it, right?

I can just say V0 goes to V1 goes to Vk goes

to U. Now I have a longer walk.

And that's a contradiction.

So I know that all the edges in which Vk is participating

are actually covered by the walk.

So that's a great property.

So let's write this down.

So all edges that are incident to Vk

are actually used-- traversed-- in the walk, W.

So now let's have a look whether we

can show that it's a walk that goes all the way around.

So let's try to prove this statement.

So let me repeat this over here.

So what we want to show is that Vk equals V0.

So given this statement, do you have any idea

how we could possibly prove this,

also given what we have been doing over here?

Suppose this would not be the case, right?

So suppose the start and the end node in this walk

are not equal to one another.

So what can we do here?

So maybe there's some suggestions?

I already had you once.