0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ "with an added vertex and 7 added edges" - how do you determine thes seven edges? $\endgroup$ – Hagen von Eitzen Nov 28 '14 at 14:25
  • $\begingroup$ 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? $\endgroup$ – jreing Nov 28 '14 at 14:35
  • 1
    $\begingroup$ Can you obtain $K_{100}$ from a graph with $99$ vertices by adding a vertex and seven edges? $\endgroup$ – Hagen von Eitzen Nov 28 '14 at 14:38
  • $\begingroup$ $5(n-1)-14 = 5n-19$, not $5n-21$. $\endgroup$ – Ashwin Ganesan Nov 28 '14 at 14:51
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – bof May 12 at 4:21
  • 1
    $\begingroup$ $$|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$$ $\endgroup$ – bof May 12 at 4:30
  • 1
    $\begingroup$ $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$. $\endgroup$ – bof May 12 at 4:37

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.