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?