PROFESSOR: So now we start on another topic in graph theory,
namely the topic of simple graphs.
So last week we were talking about directed graphs
where the arrows have a beginning and an end,
as shown here.
But simple graphs are simpler.
The edges don't have direction.
They just correspond to a mutual connection, which is symmetric.
So there's a picture of a simple graph,
and the edges are shown without an arrowhead.
A special thing about directed graphs
is that it's possible to have an arrow going
in each direction between two vertices.
But when we have undirected edges like this,
that doesn't happen.
So there's only one edge between a pair
of vertices in a simple graph.
In addition, a directed graph might
have a self loop, an edge that starts and begins
at the-- starts and ends at the same vertex.
And those are also disallowed in simple graphs.
Now, you could allow those things.
There's a thing called multi-graphs
where there are multiple edges between vertices.
And there could also be self loops, but we don't need those.
Let's not complicate matters.
We're talking about simple graphs.
OK, so the formal definition of a simple graph
is that it's an object G that has a bunch of parts.
Namely it has a nonempty set, v of vertices,
just like directed graphs.
And it has a set E of edges, but the edges now
are somewhat different since they don't have beginnings
and ends.
An edge just has two endpoints that are in V,
and we don't distinguish the endpoints.
So let's just draw a picture.
Here's a case where there are six vertices V shown in blue,
and there are these undirected edges shown in green.
In this case I see seven edges in E.
There is an example of an edge that goes between two vertices
that I've highlighted in yellow and red.
And we've made that particular edge dark green.
An edge like that can formally be represented
as just the set of its end points, a set of two things,
red and yellow.
In text, we'll often indicate it as the two vertices connected
by a horizontal bar.
But you have to remember that the order in which
the red and the yellow occur don't
matter, because it's really a set consisting
of red and yellow.
When two vertices are connected by an edge,
they are said to be adjacent.
And the edge is said to be incident
to its end points, just a little vocabulary that we use here.
A basic concept in graph theory, which
is what we're going to make a little bit
of in this video segment, is the idea of the degree of a vertex.
The degree of a vertex is simply the number of incident edges,
the number of edges, that touch it,
the number of edges for which its an end point.
So let's look at the red vertex.
There are two edges incident to the red vertex,
so its degree is 2.
OK, let's look at the yellow vertex.
Here there are four edges incident to the yellow vertex,
so its degree is 4.
No surprises yet.
So let's examine some properties of vertex degrees
that are motivated by a simple example.
Suppose I asked the question, is it
possible to have a graph with vertex degrees of 2, 2, and 1.
So implicitly it's a 3 vertex graph.
And one vertex has degree 2, another has degree 2,
and one has degree 1.
Well let's see what it looks like.
If I'm going to have a vertex of degree 1,
then I know what it looks like.
There's the vertex.
It's got one edge out of it.
It's going to some other vertex.
Now this other vertex must have degree 2,
so it's connected to something else.
And the something else must be another vertex with degree 2,
because those are the only possible spectrum of degrees,
1, 2, and 2.
And that means that this last guy
has to have an edge out of it, because it's degree 2.
And it can't go back to 2, because there's already
an edge between these two.
And it can't go back to 1, because that has degree 1.
So we're stuck.
And by this ad hoc reasoning we figured out
that there can't be a degree 3 graph with this spectrum
of degrees 2, 2, 1.
It's impossible.
Well, we could have reasoned more generally.
And there's a very elementary property of degrees
that we're going to actually make something of in a minute.
And it's called the handshaking lemma.
It says that the sum of the degrees
summed over all the vertices is equal to twice
the number of edges.
There it is written as a formula,
twice the number of edges.
So that's the cardinality symbol.
Absolute value of a set means the size of the set.
E here is finite.
Twice the number of edges is equal to the sum
over all the vertices of the degree of the vertices.
Why is that true?
Well, if you think about it, in the sum on the right,
every edge is counted twice, once for each vertex
that it's the end of.
So we're really just count-- and this
is a way of summing up over all of the vertices
in which each vertex gets numerated twice.
So the sum is twice the number of vertices.
And the proof is trivial, but let's make something of this.
You might wonder why it's called the handshaking lemma.
That will emerge in some problems
that we're going to have you do.
But let's go on and apply the handshaking lemma
in an interesting way.
And by the way, of course, since 2 plus 2 plus 1 is odd,
we could have without that ad hoc analysis figured out
that the sum of the degrees can't be odd,
because it's twice something.
All right, so here's the applications
designed to get your attention.
It is an application of graph theory to sex.
And we ask the question, are men more promiscuous than women?
And there have been repeated studies
that are cited in the notes that show again and again that when
they survey collections of men and women
and ask them how many sexual partners they have,
it's consistently the case that the men are assessed to have
30% more, 75% more, sometimes 2 and 1/2 times,
3 times as many partners as the women.
And there's got to be something wacky about this.
We're going to come up with a very elementary graph
theoretic argument that says that this is complete nonsense.
By the way, the most recent study that we could find
was one that's mentioned in the notes in 2007
by the US Department of Health.
And the statistician who collected the data
knew that the results were impossible.
But her job was to report the data, not
to explain it or interpret it.
And the men reported 30% more partners than the women.
And we're going to show that somebody is lying.
Here's how we're going to do it.
We're going to model the relationships between men
and women by having a graph that comes in two parts.
It's going to be called a so-called bipartite graph.
So there's going to be one set of vertices called
M and another set of vertices called F. M for men
and f for women, or females.
And we're going to have edges going between men and women,
between M's and F's, precisely when they have been involved
in a sexual liaison.
So looking back at this graph, this edge from that blue M
to that orange F indicates that they had a sexual liaison.
They were partners.
OK, so this is a simple graph structure
that we can use to represent who got together
with whom in any given population of men and women.
Now, if you think about the same argument
that we use for handshaking, if you sum the degrees of the men,
you're counting each edge exactly once.
And so the sum of the degrees of the men
is equal to the number of edges in this graph.
And likewise, if you sum over the females,
you're counting each edge once.
And so the sum of the female degrees
is also equal to the number of edges.
In particular, the sum over the degrees of the males
is equal to the sum over the degrees of the females.
Because every time there's a liaison,
it involves one male, one female.
All right, now let's just do a little bit
of elementary arithmetic.
I'm going to divide both sides of this equality
by the size of the male population,
by the number of men.
And if I do that, I get this formula.
The left hand side is the number of-- is
the sum of the degrees of men divided by the size of the M
population.
And here I'm doing a little trick.
Notice that the F's cancel out.
But I've expressed some of the female degrees divided
by M as the sum of the female degrees divided by F times
this factor F over M, which is the ratio of the populations
of women to men.
Now the reason I'm doing this is that if you
look at this thing on the left, this is
the average degree of the men.
This is the sum of all the degrees of men
divided by the number of men.
So it's the average number of partners that men have.
And likewise, now you can recognize over here
that I've got the average number of partners
that each woman has.
And what we've just figured out then
is that there's a fixed relationship
between the average number of partners of men,
the average degree of the M vertices
and the average degree of the F vertices.
And these two average degree, these average numbers
of partners, is simply related by the ratio
of the populations.
The men degree is the female population
divided by the M population times the average degree
of the females.
Now, what this tells us is that these wild figures
of twice as many, and 30% more, and so on
are completely absurd.
Because we know a lot about the ratio of females
to males in the population.
As a matter of fact, in the US overall
there are slightly more women than men.
There is 1.035 women for each man in the US population.
And that tells us then that if you surveyed
the population of all the men and women in the country,
you would discover that the men looked 3 and 1/2 percent more--
had 3 and 1/2 percent more partners than women per man.
But this has nothing to do with their behavior, or promiscuity,
or lack of it.
It's simply a reflection of the ratio of the populations.
Which gets us to the question of,
where do these crazy numbers come from?
And the answer seems to be that people are lying.
One explanation would be that men exaggerate
their number of partners, and women understate
their number of partners.
But the truth is that nobody knows
exactly why we get these consistently false numbers.
But we do get them consistently in one survey after another.
You will no longer be fooled by such nonsense.