2
$\begingroup$

In a $78$ member company everyone knows at least $5$ others. We sit them around 6-person tables. Prove that in every case there is a seating when at least at one table everybody knows his neighbors.

I think it's a proof by contradiction. Assume that the graph where the vertices are the people and the edges are the relation has no $6$ long cycle. How does it limit the sum of the degree?

$\endgroup$
0
$\begingroup$

It's false.

First, make 15 5-cliques, to cover 75 people. Divide these into 3 sets of 5 cliques, and add one person to each.
The extra person knows 1 person in each clique.

These 3 disconnected graphs have no 6-cycles.

$\endgroup$
0
$\begingroup$

The counterexample seems to be incorrect. Those in the 5-cliques not being connected to any of the 3 extra persons have only 4 acquaintances.

$\endgroup$

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.