Graphs with many large degrees (Q5946758)

The author proves the following results:NEWLINENEWLINENEWLINE(1) Let \(k,n,\lambda\in\mathbb{N}\), \(\lambda\geq k-1\), and \(n\geq \lambda+1\). Then NEWLINE\[NEWLINE(k,n,\lambda)= \min\Biggl\{\Biggl\lfloor{(n- k)(k-1)\over \lambda-k+1}\Biggr\rfloor, n-(\lambda- k+1)\Biggr\}.NEWLINE\]NEWLINE (The right-hand side is defined to be \(n-(\lambda-k+1)= n\) for \(\lambda=k-1\).)NEWLINENEWLINENEWLINE(2) Every nonempty graph \(G\) has a subgraph \(H\) with \(\delta(H)> \mu(G)/3\).NEWLINENEWLINENEWLINE(3) Every graph \(G\) satisfies \(\text{MAD}(G)\geq{2\over 3} \mu(G)\). That is, every graph \(G\) has a subgraph \(H\) with \(t(H)\geq {2\over 3}\mu(G)\). In general, for \(0\leq q< 1\), \(\text{MAD}(G)\geq {2-2q \over 2-q} \mu_q (G)\), and hence, if \(G\) is nonempty then \(\text{MMD}(G)> {1-q \over 2-q} \mu_q(G)\).NEWLINENEWLINENEWLINE(4) Every nonempty graph \(G\) has a subgraph \(H\) such that \(t(H)\geq{2\over 3} \mu(G)\) and \(\delta(H)>{1\over 2} t(H)\).