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.
Answer
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$.
No comments:
Post a Comment