1
$\begingroup$

I am struggling with 9.31 from A Walk Through Combinatorics by Miklos Bona. The problem statement reads:

There are several people in a classroom; some of them know each other. It is true that if two people know the same number of people in the classroom, then there is nobody in the classroom both these people know. Prove that there is someone in the classroom who knows exactly one other person in the classroom.

I realized that the second sentence of this means that if two vertices have the same degree, the sets of their neighbors are disjoint. I am not sure how to proceed past this point, however. Any help or direction would be appreciated.

$\endgroup$
  • $\begingroup$ This may be related to Ramsey theory. $\endgroup$ – user99680 Nov 6 '13 at 0:43
  • $\begingroup$ Okay, that isn't something I have learned in class, but that seems like a start. A quick wiki search tells me that problems like this start by asking "how many elements of some structure must there be to guarantee that a particular property will hold?" I can see that it must start where n=3, because two vertices are connected by one edge and there is one unconnected vertex. $\endgroup$ – Scott Nov 6 '13 at 0:52
2
$\begingroup$

Hint. I guess "some of them know each other" means that $\Delta(G)\gt0$ where $\Delta(G)$ is the maximum degree. Let $v$ be a vertex of degree $\Delta(G)$. Let $w_1,w_2,\dots,w_{\Delta(G)}$ be the neighbors of $v$; what can you say about their degrees?

$\endgroup$
  • $\begingroup$ What I get from this is that the degrees of $w_1, ...w_\Delta G$ are at least 1. In the case where $v$ and $w_i$ is the entire graph, any of the $w_i$ can be used as the answer to my proof, but I'm not sure how I expand that to where these few vertices are NOT the entire graph.. $\endgroup$ – Scott Nov 6 '13 at 4:17
  • $\begingroup$ Can $w_1$ and $w_2$ have the same degree? $\endgroup$ – bof Nov 6 '13 at 4:19
  • $\begingroup$ They cannot, because they share a common neighbor, which is $v$. So this means that the $w_i$ vertices must either have only $v$ as a neighbor, or be connected to vertices outside the set of those we have mentioned. Eventually, if this process repeats, essentially setting different vertices as $v$, you will reach a leaf vertex which has only one neighbor. Is this a sensible proof? $\endgroup$ – Scott Nov 6 '13 at 5:31
  • $\begingroup$ I don't know; it's too complicated, I don't understand it. What I mean is that, since the degrees of $w_1,\dots,w_{\Delta(G)}$ are all different, and those degrees all lie in the set $\{1,\dots,\Delta(G)\}$, they must take all values in that set; say $\Delta(G)=5$, you can't take $5$ different elements from the set $\{1,2,3,4,5\}$ without using them all. Therefore, one of the neighbors of $v$ must have degree $1$. Likewise, for each integer $k$ such that $1\le k\le\Delta(G)$, there must be a vertex of degree $k$. $\endgroup$ – bof Nov 6 '13 at 7:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.