Proof of simple graph using pigeonhole theorem

Question

Statement : Any simple graph G with $$ {\huge\Sigma}_{v\in V} {d(v)\choose{2}} > {{n}\choose{2}} $$ contains a quadrilateral.

Proof: Denote by p₂ the number of length two in G, and by p₂(v) the number of such paths whose central vertex is v.

Clearly $$p_2={d(v)\choose{2}}.$$

As each path of length two has a unique central vertex,$$p_2={\Sigma}_{v\in V}\:p_2(v)=\Sigma_{v\in V}{d(v)\choose{2}}.$$

On the other hand, each such path also has a unique pair of ends. Therefore the set of all paths of length two can be partitioned into$${n}\choose{2}$$subsets according to their ends. The hypothesis $$\Sigma_{v\in V}{{d(v)}\choose{2}}>{{n}\choose{2}}$$now implies, by virtue of the Pigeonhole Principle, that one of these subsets contains two or more paths; that is, there exist two paths of length two with the same pair of ends.

The union of these paths is a quadrilateral.

I am not able to understand how set of all paths of length two can be partitioned into ${{n}\choose{2}}$ subsets. If we're choosing any 2 vertices, how can it be insured that they have length 2 ?

If you decide to downvote the question, please provide a reason so that I can rectify the mistakes.

Answer 1

Each path $u, uv, v, vw, w$ of length $2$ has two endpoints: $u$ and $w$. We partition the set of paths into $\binom n2$ subsets by the set of endpoints $\{u,w\}$.

The subset of paths corresponding to $\{u,w\}$ is the set of all paths of length $2$ between $u$ and $w$, and may be empty (if there are no such paths), have size $1$ (if there is exactly one such path), or have size $2$ or more (if there are multiple such paths).

However, since the total number of paths is greater than $\binom n2$, and we divide the set of paths into $\binom n2$ subsets, there must be a subset corresponding to some pair $\{u,w\}$ which includes at least $2$ paths: $$u, uv_1, v_1, v_1w, w\qquad \text{and} \qquad u, uv_2, v_2, v_2w, w.$$ Then the vertices $u, v_1, w, v_2$ span a quadrilateral.

Answer 2

The proof is assuming that such a graph exists with no quadrilateral, and deducing a contradiction. If a graph has no quadrilateral, it has at most $\binom n2$ paths of length two, since for each of the $\binom n2$ pairs of vertices $u,v$ there is at most one path of length two between $u$ and $v$ - if there were two such paths $uxv$ and $uyv$ then $uxvy$ would be a quadrilateral.

I think the confusion may be that it is "at most $\binom n2$", not "exactly $\binom n2$". There could be some pairs of vertices without any paths of length two, but that's not a problem.