GRAPH THEORY General Editor Peter L. HAMMER, University of Waterloo, Ont., Canada Advisory Editors C. BERGE, Universite de Paris, France M.A. HARRISON, University of California, Berkeley, CA, U.S.A. V. KLEE, University of Washington, Seattle, WA, U S A . J.H. VAN LINT, California Institute of Technology, Pasadena, CA, U.S.A. G.-C. ROTA, Massachusetts Institute of Technology, Cambridge, MA, U.S.A. NORTH-HOLLAND PUBLISHING COMPANY - AMSTERDAM NEW YORK OXFORD NORTH-HOLLAND MATHEMATICS STUDIES 62 Annals of Discrete Mathematics (13) General Editor: Peter L. Hammer University of Waterloo, Ont., Canada Graph Theory Proceedingsof the Conference on Graph Theory, Cambridge Editor: Bela BOLLOBAS Department of Pure Mathematics and Mathematical Statistics University of Cambridge Cambridge CB2 lSB, England 1982 NORTH-HOLLAND PUBLISHING COMPANY - AMSTERDAM NEW YORK OXFORD North-Holland Publishing Company, 1982 AII rights reserved. N o part of this publication may be reproduced, stored in a retrievalsystem or transmitted,in any otherform or by any means, electronic, mechanical, photocopying, recording or otherwise, without theprior permission of the copyright owner. ISBN: 0 444 86449 0 Publishers: NORTH-HOLLAND PUBLISHING COMPANY AMSTERDAM NEW YORK OXFORD Sole distributors for the U.S.A.and Canada: ELSEVIER SCIENCE PUBLISHING COMPANY, INC. 52 VANDERBILT AVENUE, NEW YORK, NY 10017 Library of Congress Calaloging in Publication Data Main entry under t i t l e : Graph theory. (Annals of d i s c r e t e mathematics ; U) (NorthHolland mathematics studies ; 62) Papers presented a t the Cambridge Graph Theory Conference, held a t T r i n i t y College 11-l.3 Mar. p81. 1. Graph theory--Congresses. I. Bollob&, Bela. 11. Cambrid e Gra h Theory Conference (1 81 : T r i n i t y Colfege, e n i v e r s i t y of Cambridge? 111. Ser i e s . I V . Series: North-Holland mathematics s t u d i e s ; 62. QA166.G718 1982 5ll'.5 82-8098 ISBN 0-444-86449-0 AACF2 PRINTED IN TH