# prove that every graph with $n\ge7$ vertices and at least 5n-14 edges contains a sub graph with minimum degree at least 6

Question: prove that every graph with $$n\ge7$$ vertices and at least 5n-14 edges contains a sub graph with minimum degree at least 6.

My proof: By induction. For n=7, the number of edges is 21=$$7 \choose 2$$ which implies this is the full graph, so each degree is 6, and therefore the min degree as well. Now using the induction hypothesis, proof for n: A graph G with n vertices and 5n-14 edges, can actually be thought of as a graph G' with n-1 vertices with 5(n-1)-14=5n-21 edges, with an added vertex and 7 added edges. Since the hypothesis is true for n-1, then adding this vertex and the 7 edges won't decrease the min degree.

I want to know if this proof suffices or am I missing something?

• "with an added vertex and 7 added edges" - how do you determine thes seven edges? Nov 28 '14 at 14:25
• I'm assuming I have a graph with 5n-14 edges (n sized), but I can also look at it as an n-1 sized graph with 5(n-1)-14 edges + 7 edges and a vertex. Can't I? Nov 28 '14 at 14:35
• Can you obtain $K_{100}$ from a graph with $99$ vertices by adding a vertex and seven edges? Nov 28 '14 at 14:38
• $5(n-1)-14 = 5n-19$, not $5n-21$. Nov 28 '14 at 14:51

For the induction step: Consider $G$ with $n$ vertices. If all vertices of $G$ have degree $\ge 6$, $G$ itself is a subgraph as required. Otherwise, $G$ has a vertex $v$ of degree $\le 5$, and then $G':=G-v$ has $n-1$ vertices and $5n-14-\rho(v)\ge 5(n-1)-14$ edges, hence by induction hypotheses $G$' contains a subgraph with minimum degree $\ge 6$. As this is also a subgraph of $G$, we are done.

Let $$G=(V,E)$$ be a graph of order $$n\ge7$$. If every subgraph has a vertex of degree $$\lt6$$, then we can list the vertices as $$V=\{v_1,\dots,v_n\}$$ where $$v_i$$ has degree $$f_i\lt6$$ in the subgraph induced by $$\{v_i,\dots,v_n\}$$. Since $$f_i\le5$$ for all $$i$$, and since $$f_n+f_{n-1}+f_{n-2}+f_{n-3}+f_{n-4}\le0+1+2+3+4=10$$, it follows that $$|E|=f_1+\cdots+f_n\le5(n-5)+10=5n-15\lt5n-14$$. Therefore, if $$|E|\ge5n-14$$, then $$G$$ must have a subgraph with minimum degree $$\ge6$$.

More generally, if $$G=(V,E)$$ is a graph of order $$|V|=n\gt d$$, and if $$|E|\gt(d-1)n-\binom d2$$, then $$G$$ has a subgraph with minimum degree at least $$d$$.

• Choose $v_1$ of degree $\le5$ in $G$. Then choose $v_2$ of degree $\le5$ in $G-v_1$. Then choose $v_3$ of degree $\le5$ in $G-v_1-v_2$. Continue in this way until all vertices have been listed.
– bof
May 12 '19 at 4:21
• $$|E|=\sum_{i=1}^nf_i\le\sum_{i=1}^n\min(5,n-i)=\sum_{i=1}^{n-5}5+\sum_{i=n-4}^n(n-i)=5(n-5)+10=5n-15$$
– bof
May 12 '19 at 4:30
• $f_i$ is the degree of $v_i$ in the subgraph of $G$ induced by $\{v_i,\dots,v_n\}$, that is, $f_i$ is the number of edges in $G$ of the form $v_iv_j$ with $i$ fixed and $j\gt i$, so each edge of $G$ is counted exactly once in $\sum f_i$.
– bof
May 12 '19 at 4:37