I am baffled by the following solution to the problem from the Proofs from the Book. I was struggling with understanding the condition of not having a 4-cycle (C4) inside the graph. It seems to me to be a complete miracle that the absence of C4 is equivalent to the statement that every pair of vertices has at most one common neighbor. More precisely, the simplicity of the defining equation is very surprising to me and I would like to ask if this 'method' is generalizable.

Can one construct analogous inequalities for longer cycles in a similar fashion? Is it just luck that we can easily describe this short cycle globally?


enter image description here

(The maximum is found using this inequality, Cauchy-Schwartz, and the Handshaking lemma.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.