Graphs with many large degrees (Q5946758)

The author proves the following results: (1) Let \(k,n,\lambda\in\mathbb{N}\), \(\lambda\geq k-1\), and \(n\geq \lambda+1\). Then \[ (k,n,\lambda)= \min\Biggl\{\Biggl\lfloor{(n- k)(k-1)\over \lambda-k+1}\Biggr\rfloor, n-(\lambda- k+1)\Biggr\}. \] (The right-hand side is defined to be \(n-(\lambda-k+1)= n\) for \(\lambda=k-1\).) (2) Every nonempty graph \(G\) has a subgraph \(H\) with \(\delta(H)> \mu(G)/3\). (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)\). (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)\).