Hint:

This can be done by double counting. Consider a graph $G=(H,V) $, and $|H|=91$ and $|V|=456$. Let there is no set of $4$ vertices satisfies the condition. Then for each pair of vertices, there is at most $1$ vertex connects to both of them. Count the number $S $ of triplets $(X,Y,Z) $ such that $Z $ connects to $(X,Y) $ Denote $a_1,a_2,\ldots,a_{91} $ as the degree of each vertices then $a_1+...+a_{91}=2.456=912$ $S=\binom {a_1}{2}+\binom {a_2}{2}+\ldots+\binom {a_{91}}{2}=\frac {(a_1^2+\ldots+a_{91}^2)-912}{2}>=\frac {\frac {912^2}{91}-912}{2}>45.91$

Claim wrote: For any simple graph on 91 vertices, you can find 91 numbers that generate that graph (just assign a prime to each vertex, and a prime to each edge too; the number assigned to the vertex will be the product of the primes on the edges incident to it, and the prime written on the vertex itself). We need to put $n=91$, and will get $455$ on RHS $< 456$

Physicsknight wrote: 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.$ https://artofproblemsolving.com/community/c6h1938363p13337680

Where are the other posts and generalisations(posted by CantonMathGuy and biomathematics)?

Isn't there any other soln other than graph theory

You may see the official solution. They have translated the problem in a similar manner, though. And I don't think GT is used in the solution except for translating it. It's mainly double counting

@Physicsknight provided a graph theory solution. I shall provide another. So here goes. Solution. Consider the integers to be $a_1,a_2,...a_91$ Consider a graph G=(A,B) where $|A| = 91, |B| \geq 456$ Let the ith vertex represent integer $a_i$. Let $v_i$ be the degree of each vertex. So we have $\sum_{i=1}^{91} v_i >= 2*456= 912.$ By pigeon hole principle there exists a vertex k that has at least degree $v_k>=11$ Lemma: There at least 10 vertices with degree 10. Proof: If the statement is not true then $\sum_{i=1}^{91} v_i <= 912$ a contradiction. Let $A_i$ be the set of vertices with which vertex j shares an edge. So by lemma $\cap_{i=k_1}^{k_n} A_i = \phi$ holds for $n\leq 9$. Also call all vertices j in the previous relation to have property P. So at least 1 vertex doesn't have this property P. Now if this vertex is k then we are done by PHP that is two points $\in A_i$ for some i must be connected to the tenth point. Now if k belongs to some $A_i$ for some i then we shall prove the required. Note that $\cup_{i=1}^{10} A_i = \{ a_i | i =1,2,...,91\}$ as in the extremal case. We shall consider this as if the above relation violates we will again be done by the PHP as the $|A_i|=10$ for each i and $|A|=91$ Now by PHP again there will exist some $j\in \{1,2,..10\}$ for which $A_j$ for which k will share two vertices belonging to $A_j$ and we are done

Ohh.. I noticed this while studying Double Counting from Pranav Sriram Combinatorics.... This Question is exactly same as that ask in INDIA TST 2001 , which states to show that Let $G$ be a graph with $E$ edges, $n$ vertices and no $4$ cycles, then $$ E \le \frac{n (\sqrt{4n-3} +1)}{4} $$ Here just assume the Contrary and then contradict by putting $E= 456$ and $n = 91$ , to get $455 \ge 456$..

This is a graph theory problem which says that for a graph with $91$ vertices and $456=5*91+1$ edges, we'll always have a cycle of $4$. We can prove it generally for all $n$ vertice graph where $\binom{n}{2}>5n+1 \iff n \geq 12$. A graph is clique if all vertices are connected to all other vertices. That is $\binom{n}{2}$ edges in a $n$ point graph. We are removing $\binom{n}{2}-5n-1$ edges. We have $\binom{n}{4}$ cycles of $4$ and each edge is part of $\frac{\binom{n}{4}}{\binom{n}{2}}$ cycles. This means, We can at a maximum remove $\frac{\binom{n}{4}}{\binom{n}{2}}*(\binom{n}{2}-5n-1)$ cycles of $4$. Thus, we claim $\frac{\binom{n}{4}}{\binom{n}{2}}*(\binom{n}{2}-5n-1) < \binom{n}{4}$ $\iff 1-\frac{5}{n-1}-\frac{2}{n(n-1)} < 1$ $\iff 0 < \frac{5}{n-1}+\frac{2}{n(n-1)}$ This is obviously true.