In a set of 91 integers such that 456 pairs are relatively prime, 4 integers exist such that gcd(a, b) = gcd(b, c) = gcd(c, d) = gcd(d, a) = 1 This question was asked in the Indian Regional Mathematics Olympiad 2019 and was stated as:

Suppose 91 distinct positive integers greater than 1 are given such that there are at least 456 pairs among them which are relatively prime. Show that one can find four integers $\ a, b, c, d$ among them such that $\ gcd(a, b) = gcd(b, c) = gcd(c, d) = gcd(d, a) = 1 $ 

This appears to be a problem which involves the use of Pigeon-Hole Principle. However, I couldn't derive a straightforward situation of 'pigeons and boxes' that would imply a conclusion which is asked for.
Another attempt involved noticing the fact that this problems asks $\ (a, b), (b, c), (c, d), (d, a) $ to be equal to 1, which appear to be the sides of a quadrilateral ABCD. Suppose we construct 91 points in plane, no 3 of which are collinear. Each of these points represent the 91 distinct integers in our set. We show that 2 of these integers are co-prime by drawing a line connecting the respective points. We need to show that there exists a quadrilateral in this plane.
For 456 pairs to exists, there must be a point from which more than $\ [(456 * 2 - 1) / 91] $ lines are drawn, where $\ [x] $ represents Greatest Integer Function. Therefore, there must be a point from where at least 11 lines are drawn. However, I couldn't venture further to arrive at the desired conclusion. Maybe we can apply this argument recurringly in some way to the remaining set of points?
Any help would be appreciated.
 A: This is actually a graph theoretic problem! The use of GCD doesn't factor in at all. [If someone with more reputation could tag this with the relevant tags, that would be great.] Consider a graph with these 91 numbers as vertices, where two are connected iff they are coprime. Then we want to show this graph cannot be squarefree, ie it must contain a 4-cycle. There is apparently a well-known result in extremal graph theory where any quadrilateral-free graph on $n$ vertices has at most
$$\frac{n}{4}(1 + \sqrt{4n - 3})$$
edges. Note that for $n = 91$ this implies your graph can have at most 455 edges and remain squarefree, forcing our 456-edge graph to have a 4-cycle. S. Jukna has a slick proof here which he attributes to Reiman, though Reiman's original paper is in German and seems to be a more general (and much more complicated) result. 
A: Let $I_1$, $I_2$, ... ,$I_{91}$, be $91$ given positive integers. Also let $I_1$, $I_2$, ... ,$I_{91}$, are coprime to exactly $P_1$, $P_2$, ... ,$P_{91}$, number of integers(among themselves)
So we are given
$P_1+ P_2+ \dots +P_{91}=P(\text{say}) \ge  456\times2$          ......(i)
Now consider $I_j$ and $I_k$ and the numbers ($P_j$ and $P_k$ in numbers) to which they are coprime.
Among the above mentioned $P_j$ numbers the maximum number of coprimes can be
$\displaystyle{P_j \choose 2}$  ......(ii)
Similarly
Among the above mentioned $P_k$ numbers the maximum number of coprimes can be
$\displaystyle{P_k \choose 2}$  ......(iii)
Now we claim if there are no four integer as asked in the question, then the pairs of coprimes in (i) and (ii) must be disjoint, else we will have four numbers as asked in the question.
Reason for the claim:- If $p$, $q$ are two coprimes in both (ii) and (iii). Then
$$\gcd(I_j,p)=\gcd(p,I_k)=\gcd(I_k,q)=\gcd(q,I_j)=1$$
More details in Image.

