I'm trying to prove the following:
Let G be a graph with n vertices. For each two vertices x, y which are not neighbors, occurs:
d(x) +d(y) >= n
I need to prove that G has a circle with a length of 4.
I'm thinking about induction. If we have a graph with n vertices that has a circle with a length of 4, adding another vertex won't harm it. And the base of the induction is easy to find. Is this proof legal?
There is no need for induction. Also, as stated it is not entirely true. How could there be a cycle of length $4$ if $n<4$?
Assuming $n\geq 4$, take $x, y$ not neighbours. Look at the set $U$ of neighbours of $x$ and the set $V$ of neighbours of $y$. How many vertices could $U$ and $V$ at most cover (i.e. what's the maximum possible size of $U\cup V$)? Considering that adding their sizes makes at least $n$, how much overlap must they at least have? Use that to make a cycle of length $4$.
If you can't find non-neighbouring $x, y$, then your graph is complete. Because $n\geq 4$, there must be a cycle of length $4$.