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.