Consider the usual graph Qn defined by the n-dimensional cube (having 2n vertices and n2n - 1 edges). We prove that if G is an induced subgraph of Qn with more than 2n - 1 vertices then the maximum degree in G is at least ( 1 2 - o(1)) log n. On the other hand, we construct an example which shows that this is not true for maximum degree larger than.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics