Math Is Fun Forum

bossk171

Member

Registered: 2007-07-16

Posts: 305

Graph Theory

I bought a copy of "Introductory Graph Theory" bu Gary Chartrand yesterday and I'm going through it (by my self). The problem:

You and your husband go to a party with three other couples. Several Handshakes take place. No one shakes hands with themselves or their spouse. No one shakes hands with the same person more than once. After all the shaking is done, you ask every one how many hands they shook, they all give you a different answer. How many hands did you shake? How many hands did your husband shake?

The second one I'm having trouble with is:

A graph G of order p(≥2) is called "perfect" if no two of its vertices have equal degrees. Prove that "no graph is perfect."

I'm assuming that the two problems are similar in nature. Hints and helps would be better than answers, but answers would be appreciated just the same.

Thanks.

---

There are 10 types of people in the world, those who understand binary, those who don't, and those who can use induction.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Graph Theory

Set up a graph where each person is a vertex.  You can't shake hands with yourself, nor can you shake hands with the same person twice.  Therefore, such a graph is in fact a graph (i.e. not a multigraph).

Now for the first one, I assume that "After all the shaking is done, you ask every one how many hands they shook, they all give you a different answer." does not include your spouse.  If that's the case, then there is only one possibility (what is it?).

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Graph Theory

The second is easy, so long as you don't make the boneheaded mistake that I did.

What's the maximum degree of any vertex in a graph with n vertices? (Hint: It is NOT n)

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

bossk171

Member

Registered: 2007-07-16

Posts: 305

Re: Graph Theory

Oh, right, the second is easy... Assume the first vertex has a degree of (n-1) and the next has a vertex of (n-2) so on until the second to last one has only one vertex which means that the last one has to be a repeat. I'm kind of kicking myself for not seeing that before... Thanks.

I paraphrased the problem (too lazy to type word for word) but it does say: "...suppose you ask each person, including your husband..." does that mean that there's more than one answer?

---

There are 10 types of people in the world, those who understand binary, those who don't, and those who can use induction.

bossk171

Member

Registered: 2007-07-16

Posts: 305

Re: Graph Theory

I think I have it:

My thought process is this: The highest degree vertex there can be is 6 (because there's 8 total and you can't shake two hands {your own and your spouse's}) The minimum is 0, which has to be the 6's wife (because all others have already shook hands once. I can really explain it, but I think that the general rule here is if you shake hands n times, your spouse shakes hands (6-n) times.

Seeing how everyone gives you a different answer, that means that you are the one that repeats (we know that at least one repeats because of the other problem). and the only number that repeats is 3 (because 6-3=3) so both you and your spouse shook three hands. Is that the only answer?

---

There are 10 types of people in the world, those who understand binary, those who don't, and those who can use induction.

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Graph Theory

Oh, right, the second is easy... Assume the first vertex has a degree of (n-1) and the next has a vertex of (n-2) so on until the second to last one has only one vertex which means that the last one has to be a repeat.

Not necessarily. If the last vertex had a degree of 0 then there would be no repeats. But if that was the case then the first vertex couldn't be of degree (n-1), so it's still can't happen.

I'm pretty sure your answer to the puzzle is the only one.
You're right that 0 has to be married to 6, but once those two are fixed, 1 can't shake anyone else and 5 has to shake all but one of everyone else and so those two have to go together as well.

Similarly, after putting 1 and 5 together, 2 and 4 have to match up.

---

Why did the vector cross the road?
It wanted to be normal.