Proof related to maximum degree of node in a graph So I'm given this problem - Prove that in every graph with 25 vertices, in which holds that in every 3-subset of vertices, at least two of them are connected, there exists a node of degree at least 12. I tried proving this by contradiction, by counting what is the least number of edges this graph has to have, given upper conditions. I didn't think much, and I said - well, at least, it has to have as many edges as it has 3 subsets of 25 nodes. However, I don't think this is true anymore, at least I can't figure out how to prove this, as some edges may repeat through these subsets. Then, I could show that if a three subset has only one edge, no other 3 subset will have this edge as its only edge. Is this sufficient to prove what I thought before? I'm pretty confused right now, so any help would be appreciated.
 A: Hint: Fix two vertices and consider the triples that include them.

Call the vertices $v_1$ and $v_2$.


Let $u$ be a different vertex. We have at least one of the edges $uv_1$, $uv_2$ and $v_1v_2$. So each of the $23$ vertices not equal to $v_1$ or $v_2$ contributes at least $1$ to $\deg(v_1)+\deg(v_2)$, giving us $\deg(v_1)+\deg(v_2) \geq 23$.

Hint for an alternative approach: Pick some vertex $v$ of degree $\lt 12$ and consider the subgraph given by the vertices not adjacent to $v$.
A: Fix a node. There are 12 pairs of nodes left which makes 12 triplets of nodes which have only our original node in common. Apply the fact that triplets of nodes have at least two edges to these triplets. How many edges are guaranteed to be connected to our original node?
A: Complement the graph; "at least two connected by an edge" for every three vertices in the original graph becomes "triangle-free" in the complemented graph, and the maximum possible minimum degree for a triangle-free graph on $25$ vertices is $12$ in $K_{12,13}$. (Otherwise the Turán bound is exceeded.) Complementing back shows the given result (maximum and minimum swap, the sum of $\deg_G(v)$ and $\deg_{\overline G}(v)$ must be $25-1=24$ and so on).
