### Abstract

Consider the usual graph Q^{n} defined by the n-dimensional cube (having 2^{n} vertices and n2^{n - 1} edges). We prove that if G is an induced subgraph of Q^{n} with more than 2^{n - 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.

Original language | English (US) |
---|---|

Pages (from-to) | 180-187 |

Number of pages | 8 |

Journal | Journal of Combinatorial Theory, Series A |

Volume | 49 |

Issue number | 1 |

DOIs | |

State | Published - Sep 1988 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics

## Fingerprint Dive into the research topics of 'On induced subgraphs of the cube'. Together they form a unique fingerprint.

## Cite this

Chung, F. R. K., Füredi, Z., Graham, R. L., & Seymour, P. (1988). On induced subgraphs of the cube.

*Journal of Combinatorial Theory, Series A*,*49*(1), 180-187. https://doi.org/10.1016/0097-3165(88)90034-9