Introduction to Topology and Geometry E-Book

Saul Stahl

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Serie: Wiley Series in Pure and Applied Mathematics
• Sprache: Englisch

Seitenzahl: 727

Veröffentlichungsjahr: 2014

Beschreibung

An easily accessible introduction to over three centuries of innovations in geometry Praise for the First Edition ". . . a welcome alternative to compartmentalized treatments bound to the old thinking. This clearly written, well-illustrated book supplies sufficient background to be self-contained." --CHOICE This fully revised new edition offers the most comprehensive coverage of modern geometry currently available at an introductory level. The book strikes a welcome balance between academic rigor and accessibility, providing a complete and cohesive picture of the science with an unparalleled range of topics. Illustrating modern mathematical topics, Introduction to Topology and Geometry, Second Edition discusses introductory topology, algebraic topology, knot theory, the geometry of surfaces, Riemann geometries, fundamental groups, and differential geometry, which opens the doors to a wealth of applications. With its logical, yet flexible, organization, the Second Edition: * Explores historical notes interspersed throughout the exposition to provide readers with a feel for how the mathematical disciplines and theorems came into being * Provides exercises ranging from routine to challenging, allowing readers at varying levels of study to master the concepts and methods * Bridges seemingly disparate topics by creating thoughtful and logical connections * Contains coverage on the elements of polytope theory, which acquaints readers with an exposition of modern theory Introduction to Topology and Geometry, Second Edition is an excellent introductory text for topology and geometry courses at the upper-undergraduate level. In addition, the book serves as an ideal reference for professionals interested in gaining a deeper understanding of the topic.

Leseprobe

Contents

PREFACE

ACKNOWLEDGMENTS

CHAPTER 1 INFORMAL TOPOLOGY

CHAPTER 2 GRAPHS

2.1 Nodes and Arcs

2.2 Traversability

2.3 Colorings

2.4 Planarity

2.5 Graph Homeomorphisms

CHAPTER 3 SURFACES

3.1 Polygonal Presentations

3.2 Closed Surfaces

3.3 Operations on Surfaces

3.4 Bordered Surfaces

3.5 Riemann Surfaces

CHAPTER 4 GRAPHS AND SURFACES

4.1 Embeddings and Their Regions

4.2 Polygonal Embeddings

4.3 Embedding a Fixed Graph

4.4 Voltage Graphs and Their Coverings

CHAPTER 5 KNOTS AND LINKS

5.1 Preliminaries

5.2 Labelings

5.3 From Graphs to Links and on to Surfaces

5.4 The Jones Polynomial

5.5 The Jones Polynomial and Alternating Diagrams

5.6 Knots and Surfaces

CHAPTER 6 THE DIFFERENTIAL GEOMETRY OF SURFACES

6.1 Surfaces, Normals, and Tangent Planes

6.2 The Gaussian Curvature

6.3 The First Fundamental Form

6.4 Normal Curvatures

6.5 The Geodesic Polar Parametrization

6.6 Polyhedral Surfaces I

6.7 Gauss’s Total Curvature Theorem

6.8 Polyhedral Surfaces II

CHAPTER 7 RIEMANN GEOMETRIES

CHAPTER 8 HYPERBOLIC GEOMETRY

8.1 Neutral Geometry

8.2 The Upper Half-plane

8.3 The Half-Plane Theorem of Pythagoras

8.4 Half-Plane Isometries

CHAPTER 9 THE FUNDAMENTAL GROUP

9.1 Definitions and the Punctured Plane

9.2 Surfaces

9.3 3-Manifolds

9.4 The Poincaré Conjecture

CHAPTER 10 GENERAL TOPOLOGY

10.1 Metric and Topological Spaces

10.2 Continuity and Homeomorphisms

10.3 Connectedness

10.4 Compactness

CHAPTER 11 POLYTOPES

11.1 Introduction to Polytopes

11.2 Graphs of Polytopes

11.3 Regular Polytopes

11.4 Enumerating Faces

APPENDIX A CURVES

A.1 Parametrization of Curves and Arclength

APPENDIX B A BRIEF SURVEY OF GROUPS

B.1 The General Background

B.2 Abelian Groups

B.3 Group Presentations

APPENDIX C PERMUTATIONS

APPENDIX D MODULAR ARITHMETIC

APPENDIX SOLUTIONS AND HINTS TO SELECTED EXERCISES

REFERENCES AND RESOURCES

Index

PURE AND APPLIED MATHEMATICS

A Wiley Series of Texts, Monographs, and Tracts

Founded by RICHARD COURANT

Editors Emeriti: MYRON B. ALLEN III, DAVID A. COX, PETER HILTON,

HARRY HOCHSTADT, PETER LAX, JOHN TOLAND

A complete list of the titles in this series appears at the end of this volume.

Copyright © 2013 by John Wiley & Sons, Inc. All rights reserved.

Published by John Wiley & Sons, Inc., Hoboken, New Jersey. All rights reserved. Published simultaneously in Canada.

No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone], or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, [phone], fax [phone], or online at http://www.wiley.com/go/permission.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representation or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services please contact our Customer Care Department within the United States at [phone], outside the United States at [phone] or fax [phone].

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print, however, may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data:

Stahl, Saul.

Introduction to topology and geometry. — 2nd edition / Saul Stahl, University of Kansas, Catherine

Stenson, Juniata College.

pages cm. — (Pure and applied mathematics)

Includes bibliographical references and index.

ISBN 978-1-118-10810-9 (hardback)

1. Topology 2. Geometry. I. Stenson, Catherine, 1972- II. Title.

QA611.S814 2013

514—dc23         2012040259

To Denise, with love from Saul

To my family, with love from Cathy.

PREFACE

This book is intended to serve as a text for a two-semester undergraduate course in topology and modern geometry. It is devoted almost entirely to the geometry of the last two centuries. In fact, some of the subject matter was discovered only within the last two decades. Much of the material presented here has traditionally been part of the realm of graduate mathematics, and its presentation in undergraduate courses necessitates the adoption of certain informalities that would be unacceptable at the more advanced levels. Still, all of these informalities either were used by the mathematicians who created these disciplines or else would have been accepted by them without any qualms.

The first four chapters aim to serve as an introduction to topology. Chapter 1 provides an informal explanation of the notion of homeomorphism. This naive introduction is in fact sufficient for all the subsequent chapters. However, the instructor who prefers a,more rigorous treatment of basic topological concepts such as homeomorphisms, topologies, and metric spaces will find it in Chapter 10.

The second chapter emphasizes the topological aspects of graph theory, but is not limited to them. This material was selected for inclusion because the accessible nature of some of its results makes it the pedagogically perfect vehicle for the transition from the metric Euclidean geometry the students encountered in high school to the combinatorial thinking that underlies the topological results of the subsequent chapters. The focal issue here is planarity: Euler’s Theorem, coloring theorems, and the Kuratowski Theorem.

Chapter 3 presents the standard classifications of surfaces of both the closed and bordered varieties. The Euler–Poincaré equation is also proved.

Chapter 4 is concerned with the interplay between graphs and surfaces—in other words, graph embeddings. In particular, a procedure is given for settling the question of whether a given graph can be embedded on a given surface. Polygonal (2-cell) embeddings and their rotation systems are discussed. The notion of covering surfaces is introduced via the construction of voltage graphs.

The theory of knots and links has recently received tremendous boosts from the work of John Con way, Vaughan Jones, and others. Much of this work is easily accessible, and some has been included in Chapter 5: the Con way–Gordon–Sachs Theorem regarding the intrinsic linkedness of the graph K6 in and the invariance of the Jones polynomial. While this discipline is not, properly speaking, topological, connections to the topology of surfaces are not lacking. Knot theory is used to prove the nonembeddability of nonorientable surfaces in , and surface theory is used to prove the nondecomposability of trivial knots. The more traditional topic of labelings is also presented.

The next three chapters deal with various aspects of differential geometry. The exposition is as elementary as the author could make it and still meet his goals: explanations of Gauss’s Total Curvature Theorem and hyperbolic geometry. The geometry of surfaces in is presented in Chapter 6. The development follows that of Gauss’s General Investigations of Curved Surfaces. The subtopics include Gaussian curvature, geodesies, sectional curvatures, the first fundamental form, intrinsic geometry, and the Total Curvature Theorem, which is Gauss’s version of the famed Gauss–Bonnet formula. Some of the technical lemmas are not proved but are instead supported by informal arguments that come from Gauss’s monograph. A considerable amount of attention is given to polyhedral surfaces for the pedagogical purpose of motivating the key theorems of differential geometry.

The elements of Riemannian geometry are presented in Chapter 7: Riemann metrics, geodesies, isometries, and curvature. The numerous examples are also meant to serve as a lead-in to the next chapter.

The eighth chapter deals with hyperbolic geometry. Neutral geometry is defined in terms of Euclid’s axiomatization of geometry and is described in terms of Euclid’s first 28 propositions. Various equivalent forms of the parallel postulates are proven, as well as the standard results regarding the sum of the angles of a neutral triangle. Hyperbolic geometry is also defined axiomatically. Poincaré’s half-plane geometry is developed in some detail as an instance of the Riemann geometries of the previous chapter and is demonstrated to be hyperbolic. The isometries of the half-plane are described both algebraically and geometrically.

The ninth chapter is meant to serve as an introduction to algebraic topology. The requisite group theory is summarized in Appendix B. The focus is on the derivation of fundamental groups, and the development is based on Poincaré’s own exposition and makes use of several of his examples. The reader is taught to derive presentations for the fundamental groups of the punctured plane, closed surfaces, 3-manifolds, and knot complements. The chapter concludes with a discussion of the Poincaré Conjecture.

The tenth chapter serves a dual purpose. On the one hand it aims to acquaint the reader with the elegant topic of general topology and the joys of sequence chasing. On the other hand, it contains the rigorous definitions of a variety of fundamental concepts that were only informally defined in the previous chapters. In terms of mathematical maturity, this is probably the most demanding part of the book.

The last chapter is devoted to the study of polytopes. Following an introduction, attention is given to the graphs of polytopes, regular polytopes, and the enumeration of faces of polytopes

Wherever appropriate, historical notes have been interspersed with the exposition. Care was taken to supply many exercises that range from the routine to the challenging. Middle-level exercises were hard to come by, and the author welcomes all suggestions.

An Instructor’s solution manual is available upon request from Wiley.

SAUL STAHL

Lawrence, Kansas

[email protected]

ACKNOWLEDGMENTS

The first author is deeply indebted to Mark Hunacek for reading the manuscript and suggesting many improvements. Jack Porter helped by making his Graduate Topology Notes and other materials available to me. He also corrected some errors in the early version of Chapter 10. Encouraging kind words and valuable criticisms were provided by the reviewers Michael J. Kallaher, David Royster, Dan Gottlieb, and David W. Henderson, as well as several others who chose to remain anonymous. Stephen Quigley and Susanne Steitz-Filler at John Wiley and Sons supervised the conversion of the notes into a book. The manuscript was expertly typeset by Larisa Martin and Sandra Reed. Prentice Hall gave me its gracious permission to reprint portions of Chapters 9–12 of my book Geometry from Euclid to Knots, which it published in 2003.

The second author is grateful to Saul Stahl for the invitation to join this project and for his help throughout. Thanks to Marge Bayer for recommending me and for her comments on a draft, and to Lou Billera for his comments and for his guidance over the years. Thanks also to the Mathematics Institute of Leiden University for their hospitality in the spring of 2012.

C. S.

CHAPTER 1

INFORMAL TOPOLOGY

In this chapter the notion of a topological space is introduced, and informal ad hoc methods for identifying equivalent topological spaces and distinguishing between nonequivalent ones are provided.

The last book of Euclid’s opus Elements is devoted to the construction of the five Platonic solids pictured in Figure 1.1. A fact that Euclid did not mention is that the counts of the vertices, edges, and faces of these solids satisfy a simple and elegant relation. If these counts are denote by v, e, and f, respectively, then

(1)

Specifically, for these solids we have:

Figure 1.1 The Platonic solids.

Figure 1.2 A lopsided cube.

Euler’s equation remains valid even after the solids are subjected to a wider class of distortions which result in the curving of their edges and faces (see Figure 1.4). One need simply relax the definition of edges and faces so as to allow for any nonself intersecting curves and surfaces. Soccer balls and volleyballs, together with the patterns formed by their seams, are examples of such curved solids to which Euler’s equation applies. Moreover, it is clear that the equation still holds after the balls are deflated.

Topology is the study of those properties of geometrical figures that remain valid even after the figures are subjected to distortions. This is commonly expressed by saying that topology is rubber-sheet geometry. Accordingly, our necessarily informal definition of a topological space identifies it as any subset of space from which the notions of straightness and length have been abstracted; only the aspect of contiguity remains. Points, arcs, loops, triangles, solids (both straight and curved), and the surfaces of the latter are all examples of topological spaces. They are, of course, also geometrical objects, but topology is only concerned with those aspects of their geometry that remain valid despite any translations, elongations, inflations, distortions, or twists.

Figure 1.3 Three solids.

Figure 1.4 A curved cube.

Another topological problem investigated by Euler, somewhat earlier, in 1736, is known as the bridges of Koenigsberg. At that time this Prussian city straddled the two banks of a river and also included two islands, all of which were connected by seven bridges in the pattern indicated in Figure 1.5. On Sunday afternoons the citizens of Koenigsberg entertained themselves by strolling around all of the city’s parts, and eventually the question arose as to whether an excursion could be planned which would cross each of the seven bridges exactly once. This is clearly a geometrical problem in that its terms are defined visually, and yet the exact distances traversed in such excursions are immaterial (so long as they are not excessive, of course). Nor are the precise contours of the banks and the islands of any consequence. Hence, this is a topological problem. Theorem 2.2.2 will provide us with a tool for easily resolving this and similar questions.

The notorious Four-Color Problem, which asks whether it is possible to color the countries of every geographical map with four colors so that adjacent countries sharing a border of nonzero length receive distinct colors, is also of a topological nature. Maps are clearly visual objects, and yet the specific shapes and sizes of the countries in such a map are completely irrelevant. Only the adjacency patterns matter.

Every mathematical discipline deals with objects or structures, and most will provide a criterion for determining when two of these are identical, or equivalent. The equality of real numbers can be recognized from their decimal expansions, and two vectors are equal when they have the same direction and magnitude. Topological equivalence is called homeomorphism. The surface of a sphere is homeomorphic to those of a cube, a hockey puck, a plate, a bowl, and a drinking glass. The reason for this is that each of these objects can be deformed into any of the others. Similarly, the surface of a doughnut is homeomorphic to those of an inner tube, a tire, and a coffee mug. On the other hand, the surfaces of the sphere and the doughnut are not homeomorphic. Our intuition rejects the possibility of deforming the sphere into a doughnut shape without either tearing a hole in it or else stretching it out and juxtaposing and pasting its two ends together. Tearing, however, destroys some contiguities, whereas juxtaposition introduces new contiguities where there were none before, and so neither of these transformations is topologically admissible. This intuition of the topological difference between the sphere and the doughnut will be confrmed by a more formal argument in Chapter 3.

Figure 1.5 The city of Koenigsberg.

Figure 1.6 Homeomorphic open arcs.

The easiest way to establish the homeomorphism of two spaces is to describe a deformation of one onto the other that involves no tearing or juxtapositions. Such a deformation is called an isotopy. Whenever isotopies are used in the sequel, their existence will be clear and will require no formal justification. Such is the case, for instance, for the isotopies that establish the homeomorphisms of all the open arcs in Figure 1.6, all the loops in Figure 1.7, and all the ankh-like configurations of Figure 1.8. Note that whereas the page on which all these curves are drawn is two-dimensional, the context is definitely three-dimensional. In other words, all our curves (and surfaces) reside in Euclidean 3-space , and the isotopies may make use of all three dimensions.

The concept of isotopy is insufficient to describe all homeomorphisms. There are spaces which are homeomorphic but not isotopic. Such is the case for the two loops in Figure 1.9. It is clear that loop b is isotopic to all the loops of Figure 1.7 above, and it is plausible that loop a is not, a claim that will be justified in Chapter 5. Hence, the two loops are not isotopic to each other. Nevertheless, they are homeomorphic in the sense that ants crawling along these loops would experience them in identical manners. To express this homeomorphism somewhat more formally it is necessary to resort to the language of functions. First, however, it should be pointed out that the word function is used here in the sense of an association, or an assignment, rather than the end result of an algebraic calculation. In other words, a function f : S → T is simply a rule that associates to every point of S a point of T. In this text most of the functions will be described visually rather than algebraically.

Figure 1.7 Homeomorphic loops.

Figure 1.8 Homeomorphic ankhs.

Figure 1.9 Two spaces that are homeomorphic but not isotopic.

Given two topological spaces S and T, a homeomorphism is a function f : S – T such that

1. f matches all the points of S to all the points of T (distinct points of S are matched with distinct points of T and vice versa);

2. f preserves contiguity.

It is the vagueness of the notion of contiguity that prevents this from being a formal definition. Since any two points on a line are separated by an infinitude of other points, this concept is not well defined. The homeomorphism of S and T is denoted by S ≈ T. The homeomorphism of the loops of Figure 1.9 can now be established by orienting them, labeling their lowest points A and B, and matching points that are at equal distances from A and B, where the distance is measured along the oriented loop (Fig. 1.10). Of course, the positions of A and B can be varied without affecting the existence of the homeomorphism.

A similar function can be defined so as to establish the homeomorphism of any two loops as long as both are devoid of self-intersections. Suppose two such loops c and d, of lengths γ and δ respectively, are given (Fig. 1.11). Again begin by specifying orientations and initial points C and D on the two loops. Then, for every real number 0 ≤ r < 1, match the point at distance rγ from C along c with the point at distance rδ from D along d.

Figure 1.12 contains another instructive example. Each of its three topological spaces consists of a band of, say, width 1 and length 20. They differ in that e is untwisted, f has one twist, and g has two twists. Band f differs from the other two in that its border is in fact one single loop whereas bands e and g have two distinct borders each. It therefore comes as no surprise that band f is not homeomorphic to either e or g. These last two, however, are homeomorphic to each other. To describe this homeomorphism a coordinate system is established on each of the bands as follows. For each number 0 ≤ r ≤ 1 let Le,r and Lg,r denote the oriented loops of length 20 that run along the band at a constant distance r from the bottom borders of e and g respectively. Choosing start lines as described in Figure 1.13, the coordinate pair (r,s), 0 ≤ r ≤ 1, 0 ≤ s < 20, describes those points on the loops Le,r and Lg,r at a distance s from the respective starting line. The required homeomorphism simply matches up points of e and g that have the same coordinate pairs. The reason this wouldn’t work for band f is that for this band the coordinatization process fails (see Fig. 1.14).

As mentioned above, f is not homeomorphic to e and g, because it has a different number of borders. In general, borders and other extremities are a good place to look for differences between topological spaces. For example, every two of the spaces in Figure 1.15 are nonhomeomorphic because they each have a different number of extremities. The number of components of a space can also serve as a tool for distinguishing between homeomorphism types. All the spaces in Figure 1.16 have the same number of extremities, but they are nevertheless nonhomeomorphic because each has a different number of components: 1, 2, 3, and 4, respectively.

Another method for distinguishing between spaces is to examine what remains when an equal number of properly selected points are deleted from each. For instance, both spaces of Figure 1.17 have one component, and neither has extremities. Nevertheless, they are not homeomorphic, because the removal of the two endpoints of the diameter of the θ-like space results in a space with three components, whereas the removal of any two points of the circle leaves only two components. In general a topological property of a space is a property that is shared by all the spaces that are homeomorphic to it. The number of endpoints and the number of components are both such topological properties. On the other hand, neither the length of an interval nor the area of a region is a topological property.

Figure 1.10 A homeomorphism of two loops.

Figure 1.11 A homeomorphism of two loops.

Figure 1.12 Three bands.

Figure 1.13 The homeomorphism of two bands.

Figure 1.14 A failed homeomorphism.

Figure 1.15 Four nonhomeomorphic spaces.

Figure 1.16 Four nonhomeomorphic spaces.

Figure 1.17 Two nonhomeomorphic spaces.

The foregoing discussion of topological spaces, homeomorphisms, and isotopies is an informal working introduction that will serve for the purposes of this text. Experience indicates that this lack of precision will not hamper the comprehension of the subsequent material. Rigorous definitions are provided in Chapter 10, which can be read out of sequence.

In working out the exercises, the readers may find it useful to note that both homeomorphism and isotopy are equivalence relations in the sense that they satisfy the following three conditions:

Reflexivity:

Every topological space is homeomorphic (isotopic) to itself.

Symmetry:

If

S

is homeomorphic (isotopic) to

T,

then

T

is homeomorphic (isotopic) to

S.

Transitivity:

If

R

is homeomorphic (isotopic) to

S

and

S

is homeomorphic (isotopic) to

T,

then

R

is homeomorphic (isotopic) to

T.

Exercises 1.1

1. Which of the letters in Figure 1.18 are homeomorphic?

2. Which of the topological spaces in Figure 1.19 are homeomorphic?

3. Which of the topological spaces in Figure 1.20 are homeomorphic?

4. Which of the topological spaces of Figure 1.21 are isotopic?

5. Are the following statements true or false? Justify your answers.

(a) If two topological spaces are homeomorphic, then they are also isotopic.

(b) If two topological spaces are isotopic, then they are also homeomorphic.

(c) Topological equivalence is synonymous with homeomorphism.

(d) Topological equivalence is synonymous with isotopy.

(e) Every two loops are isotopic.

(f) Every two loops are homeomorphic.

Figure 1.18 Twenty-six topological spaces.

Figure 1.19 Some one-dimensional topological spaces.

Figure 1.20 Some one-dimensional topological spaces.

Figure 1.21 Some one-dimensional topological spaces.

CHAPTER 2

GRAPHS

The one-dimensional topological objects are arcs. Graphs are created by the juxtaposition of a finite number of arcs, and they underlie many applications of mathematics as well as popular riddles. Traversability, planarity, colorability, and homeomorphisms of graphs are discussed in this chapter.

2.1 Nodes and Arcs

Figure 2.1 A graph.

then (deg v1. deg v2, …, deg vp) is the degree sequence of G. Thus, the degree sequence of the graph of Figure 2.1 is (7, 4, 4, 4, 2, 1, 0). The numbers of nodes and arcs of the graph G are denoted by p(G) and q(G), or simply p and q, respectively.

The first proposition describes a simple and useful relation between the degrees of the nodes of a graph and the number of its arcs.

PROOF: Each open arc of G contributes 1 to the degrees of each of its two endpoints, and each loop contributes 2 to the degree of its only node. Hence each arc contributes 2 to Σv∈N(G) deg v. The desired equation now follows immediately. Q.E.D.

This proposition immediately eliminates (3, 3, 2, 2, 1) as a possible degree sequence, since the sum of the degrees of a graph must be even.

Distinct arcs that join the same endpoints are said to be parallel, and a graph that contains neither loops nor parallel arcs is said to be simple. Of the three graphs in Figure 2.2 only the middle one is simple.

If G and G′ are graphs such that N(G) N(G′) and A (G) A(G′), then G′ is said to be a subgraph of G. If G′ is a subgraph of G, then G – G′ is the subgraph of G with node set N(G) and arc set A(G) –A(G′) (i.e., all the arcs of G that are not arcs of G′).

Exercises 2.1

1. Compute the degree sequences of the following graphs.

(a) K5 (b) Kn (c) K3,4 (d) Km,n(e) K3,2,1 (f) Kl,m,n (g) K7,6,5,4 (h) Kn1, n2, …, nk

2. Which of the following sequences are degree sequences of some graph? Justify your answer.

(a) (1, 1) (b) (2, 1) (c) (2, 2) (d) (3, 1) (e) (3, 2) (f) (3, 3) (g) (1, 1, 1) (h) (2, 1, 1) (i) (2, 2, 1) (j) (2, 2, 2) (k) (4, 2, 0) (1) (8, 0)

3. Which of the following sequences are degree sequences of some simple graph? Justify your answer.