MathDB

2

Part of 1985 Austrian-Polish Competition

Problems(1)

Graph construction given degrees

Source: Austrian-Polish 1985, Problem 2

7/5/2015
Suppose that n≥8n\ge 8 persons P1,P2,…,PnP_1,P_2,\dots,P_n meet at a party. Assume that PkP_k knows k+3k+3 persons for k=1,2,…,n−6k=1,2,\dots,n-6. Further assume that each of Pn−5,Pn−4,Pn−3P_{n-5},P_{n-4},P_{n-3} knows n−2n-2 persons, and each of Pn−2,Pn−1,PnP_{n-2},P_{n-1},P_n knows n−1n-1 persons. Find all integers n≥8n\ge 8 for which this is possible.
(It is understood that "to know" is a symmetric nonreflexive relation: if PiP_i knows PjP_j then PjP_j knows PiP_i; to say that PiP_i knows pp persons means: knows pp persons other than herself/himself.)
graph theoryvertex degreecombinatorics