 ## Subtitles section Play video

• The following content is provided under a Creative

• Your support will help MIT OpenCourseWare

• 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.

• 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?