## A Clique of Acquaintances

I thank Professor W. McWorter for bringing this problem to my attention. The problem has been posted to one of the wu:forums.

There are *n* + 1*n* of them, there is some one of the *n* + 1,*n*, acquainted with all *n*. Show that there is a person that is acquainted with every one present.

(The problem makes a tacit assumption that "being acquainted" is a symmetric relationship.)

|Contact| |Front page| |Contents| |Algebra| |Store|

Copyright © 1996-2017 Alexander Bogomolny

There are *n* + 1*n* of them, there is some one of the *n* + 1,*n*, acquainted with all *n*. Show that there is a person that is acquainted with every one present.

### Solution

The problem has been characterized as a *quickie*: once you hit on the right idea, the solution takes just a few lines.

The problem has a natural representation as a graph: two nodes are connected by an edge iff the fellows they represent are acquainted. The nice idea that makes the problem a quickie is that, under the conditions of the problem, there is always a *clique* of size at least *n* + 1.

Let's first show that the existence of a clique C of size *n* + 1

Now, let's form a clique of size *n* + 1.*n* nodes. There is a node that is connected to each of the selected ones. This one, along with any of the selected, form a clique of size 2. Arbitrarily add * n - 2* nodes to these two. There is a node that is connected to each of the selected ones. Along with a 2-clique it forms a 3-clique. We may continue in this manner until we get an

*n*-clique. For this, as for any collection of

*n*nodes, there is a node connected to each of the selected ones. Together they form an (

*n*+ 1)-clique.

A short while after posting this page I found that the problem was proposed in 2006 at the *American Math Monthly* by Ashay Burungale from India, with two solution published in 2008 (v. 115, n. 9, p. 862). The first solution by Kenneth Schilling is a paraphrase of the above. Another (by Christopher Carl Heckman) is essentially different.

We prove the contrapositive: If nobody knows everyone, then some set A of n citizens is not completely known by anyone outside A. We first color each citizen red or green as follows. If p is not yet colored, choose some p' unknown to p. If p' is already colored, give p the opposite color. Otherwise, give p and p' opposite colors. At the end, everyone has a color opposite from that of someone he or she does not know. The less-frequent color occurs at most n times; let A be a set of size n including all those with that color. Each person outside A has the other color and hence does not know everyone in A.

The two solutions were followed by

**Editorial comment**. The problem of course is a statement about graphs (perhaps the popularity of the problem stemmed from not using that language). In the language of graph theory, it states that a graph of odd order has a vertex adjacent to all others if each set with fewer than half the vertices has a common neighbor. Several solvers did use graph theoretic language and arguments.

- Graphs Fundamentals
- Crossing Number of a Graph
- Regular Polyhedra
- 3 Utilities Puzzle: Water, Gas, Electricity
- A Clique of Acquaintances
- Round Robin Tournament
- The Affirmative Action Problem
- The Two Men of Tibet Problem
- Euler Cycles in Digraph
- Fleury's Algorithm and Euler's Paths and Cycles: an Interactive Gizmo
- Graph with Nodes of Even Degree
- Graph without 3-Cycles

|Contact| |Front page| |Contents| |Algebra| |Store|

Copyright © 1996-2017 Alexander Bogomolny

61155415 |