Prove that described graph contains $K_{2, t}$ as spanning subgraph

Question

Let us consider graph $G$ that doesn't have multi edges and loops. Let it satisfy following inequality

$$\sum_{x\in V(G)} \binom{\deg(x)}{2} \ge (t - 1) \cdot \binom{n}{2} + 1$$

then prove that $G$ has spanning subgraph that is $K_{2,t}$

I had a few observations that may be handy when proving this fact but I couldn't put it all together and conclude proof.

Here is my key observation (I think). It is easy to see that sum on the left of inequality clearly counts all unique $K_{1,2}$ subgraphs (we treat each vertex as vertex in the left part of corresponding bipartite graph and basically count all ways to choose two its' neighbours on the right part of $K_{1,2}$). Also, what is $K_{2, t}$ in terms of $K_{1,2}$? Well, if we have $K_{2,t}$ as a spanning subgraph, we clearly also have $t$ subgraphs $K_{1,2}$, its' left vertex is one of $t$ vertices (in the right part of $K_{2,t}$), and they are distinct, its' two right vertices are these two vertices on the left of $K_{2, t}$. So, all we actually need to prove here is that if inequality is satisfied, there exists $t$ $K_{1,2}$ subgraphs with distinct left parts and common right part. That would conclude the proof. However, I can't make any sense of the right part of inequality and that doesn't give me a chance to complete my thoughts.

All ideas and hints will be appreciated!

Answer 1

Note: Instead of just showing a "spanning subgraph" (which places an unnecessary constraint $ n = t + 2$), I will show that a $K_{2, t}$ subgraph exists (with no constraint on $t$).

---

Proof by contradiction. Suppose no $K_{2, t}$ exists.

Set up the incidence matrix where the rows and columns are the $n$ vertices, and the entry if 1 iff these 2 vertices are connected.

We count the number of column pairs $\begin{pmatrix} 1 \\ 1 \end{pmatrix}$ in 2 different ways.

First: Pick a column and count the number of column pairs in that column.
For column corresponding to vertex $x$ with degree $\deg(x) $, it will produce exactly $ { \deg(x) \choose 2 } $ such column pairs.

Second: Pick 2 rows and count the number of column pairs in those rows.
For any 2 vertices, since no such $K_{2, t}$ exists, these 2 vertices are both connected to at most $(t-1)$ other vertices, so the number of column pairs in those 2 rows is at most $ (t-1)$.

Hence, $\sum { \deg(x) \choose 2 } = \text{ number of column pairs } \leq ( t-1) { n \choose 2 } $.

However, this contradicts the given condition. Hence, a $K_{2, t}$ exists.

Answer 2

If $|V(G)|=n=2+t>2$, then it follows from your inequality that the degrees of at least two vertices are greater $t$. If, for example, $\operatorname{deg}(x)\leq t$ for each vertex $x\in V(G)$, then \begin{align*} nt(t-1)\\ \geq\sum_{x\in V(G)}\operatorname{deg}(x)(\operatorname{deg}(x)-1)\\ \geq(t-1)n(n-1)+2\\ \Rightarrow t\geq n-1+\frac{2}{n(t-1)}\\ \Rightarrow t\geq n \end{align*} We get a contradiction.

Slightly more accurate estimates allow us to prove that at least two vertices must have a degree greater than $t$. Then graph $G$ contains $K_{2,t}$ as a spanning subgraph.

Addition.

By the way, it is not difficult to obtain the inequality $n\geq t+2$. It follows from the obvious inequality $\operatorname{deg}(x)\leq n-1$. On the other hand, if there are no other conditions on $t$, then it does not follow from the condition that there exists a spanning subgraph $K_{2,t}$. For example, consider a regular graph $G$ of order $10$ and degree $7$. At $t=5$ we have $$ 10\binom{7}{2}>(5-1)\binom{10}{2}+1 $$ However, it is clear that $G$ does not contain $K_{2,5}$ as a spanning subgraph. Moreover, $G$ does not contain $K_{2,8}$ as a spanning subgraph. It is clear that $G$ contains $K_{2,7}$ and even more so $K_{2,5}$.