0 0 4 views

**Unformatted text preview: **

JOURNAL OF COMBINATORIAL THEORY Series A 49 180 187 1988 Note On Induced Subgraphs of the Cube F R K CHUNG Bell Communication Research Morristown New Jersey 07960 ZOLTAN F REDI AT T Bell Laboratories Murray Hill New Jersey 07974 Mathematical Institute of the Hungarian Academy of Science 1364 Budapest Pf 127 Hungary and Department of Mathematics Massachusetls Institute of Technology Cambridge Massachusetts 02139 R L GRAHAM AT T Bell Laboratories Murray Hill New Jersey 07974 AND P SEYMOUR Bell Communication Research Communicated Received Morristown by the Managing April New Jersey 07960 Editors 4 1987 Consider the usual graph Q defined by the n dimensional cube tices and n2 edges We prove that if G is an induced subgraph than 2 vertices then the maximum degree in G is at least 4 o other hand we construct an example which shows that this maximum degree larger than 1 0 1988 Academic POW inc having 2 verof Q with more 1 log n On the is not true for 1 PRELIMINARIES Denote by Q the graph of the n dimensional cube i e the vertex set of Qfl consists of all the 0 1 vectors of length n and two vectors x ye 0 l are adjacent if they differ from each other in exactly one 180 0097 3165 88 Copyright All rights 3 00 0 1988 by Academic Press Inc of reproduction in any form reserved INDUCEDSUBGRAPHSOFTHECUBE component d G i e 181 For a graph G V E we denote the maximum degree by d G us deg u The average degree d G is defined to be C Y GJdeg v l V G J We say GE Q N if G is an induced subgraph of Q with N vertices i e I V G 1 N V G E 0 I and E G E Q n V G x V G Qfl is a bipartite graph so we have a GE Q 2 without any edge namely G and GzVf where V G x 0 I C r xi 1 mod 2 V Gf 0 l V G Our main result shows that even though the average degree of a graph GE Q 2 1 can be very small only 2n 2 l these graphs must have large degree THEOREM 1 1 Let G be an induced subgraph of Q with at least 2 1 vertices Then for some vertex v of G we have deg v f log n t log log n 1 1 with On the other hand