Introduction_to_Graph_Theory-West-2e-solutions.pdf

INTRODUCTION TO GRAPH THEORY

SECOND EDITION (2001)

NOTICE

This is the Summer 2005 version of the Instructor's Solution Manual for

Introduction to Graph Theory , by Douglas B. West. A few solutions have

been added or claried since last year's version.

Also present is a (slightly edited) annotated syllabus for the one

semester course taught from this book at the University of Illinois.

This version of the Solution Manual contains solutions for 99.4% of

the problems in Chapters 17 and 93% of the problems in Chapter 8. The

author believes that only Problems 4.2.10, 7.1.36, 7.1.37, 7.2.39, 7.2.47,

and 7.3.31 in Chapters 17 are lacking solutions here. There problems are

too long or difcult for this text or use concepts not covered in the text; they

will be deleted in the third edition.

The positions of solutions that have not yet been written into the les

are occupied by the statements of the corresponding problems. These prob

lems retain the ./ , . ! / , .C/ , ./ indicators. Also ./ is added to introduce

the statements of problems without other indicators. Thus every problem

whose solution is not included is marked by one of the indicators, for ease

of identication.

The author hopes that the solutions contained herein will be useful to

instructors. The level of detail in solutions varies. Instructors should feel

free to write up solutions with more or less detail according to the needs of

the class. Please do not leave solutions posted on the web.

Due to time limitations, the solutions have not been proofread or edited

as carefully as the text, especially in Chapter 8. Please send corrections to

west@math.uiuc.edu . The author thanks Fred Galvin in particular for con

tributing improvements or alternative solutions for many of the problems

in the earlier chapters.

This will be the last version of the Solution Manual for the second

edition of the text. The third edition will have many new problems, such

as those posted at http://www.math.uiuc.edu/ west/igt/newprob.html . The

effort to include all solutions will resume for the third edition. Possibly

other pedagogical features may also be added later.

Inquiries may be sent to west@math.uiuc.edu . Meanwhile, the author

apologizes for any inconvenience caused by the absence of some solutions.

SOLUTION MANUAL

SUMMER 2005 VERSION

c DOUGLAS B. WEST

MATHEMATICS DEPARTMENT

UNIVERSITY OF ILLINOIS

or transmitted in any form without permission.

Douglas B. West

iii

Solutions

Preface

Mathematics Department - University of Illinois

Suggested Schedule

The subject matter for the course is the rst seven chapters of the text,

skipping most optional material. Modications to this are discussed below.

The 22 sections are allotted an average of slightly under two lectures each.

In the exercises, problems designated by ./ are easier or shorter than

most, often good for tests or for warmup before doing homework problems.

Problems designated by .C/ are harder than most. Those designated by . ! /

are particularly instructive, entertaining, or important. Those designated

by ./ make use of optional material.

The semester at the University of Illinois has 43 ftyminute lectures.

The nal two lectures are for optional topics, usually chosen by the students

from topics in Chapter 8.

Chapter 1 Fundamental Concepts 8

Chapter 2 Trees and Distance 5.5

Chapter 3 Matchings and Factors 5.5

Chapter 4 Connectivity and Paths 6

Chapter 5 Graph Coloring

MATH 412

SYLLABUS FOR INSTRUCTORS

Text: West, Introduction to Graph Theory, second edition,

Prentice Hall, 2001.

Many students in this course see graph algorithms repeatedly in

courses in computer science. Hence this course aims primarily to improve

students' writing of proofs in discrete mathematics while learning about

the structure of graphs. Some algorithms are presented along the way, and

many of the proofs are constructive. The aspect of algorithms emphasized

in CS courses is running time; in a mathematics course in graph theory

from this book the algorithmic focus is on proving that the algorithms work.

Math 412 is intended as a rigorous course that challenges students to

think. Homework and tests should require proofs, and most of the exercises

in the text do so. The material is interesting, accessible, and applicable;

most students who stick with the course will give it a fair amount of time

and thought.

An important aspect of the course is the clear presentation of solutions,

which involves careful writing. Many of the problems in the text have hints,

either where the problem is posed or in Appendix C (or both). Producing

a solution involves two main steps: nding a proof and properly writing

it. It is generally benecial to the learning process to provide collabora

tive study sessions in which students can discuss homework problems in

small groups and an instructor or teaching assistant is available to answer

questions and provide direction. Students should then write up clear and

complete solutions on their own.

This course works best when students have had prior exposure to

writing proofs, as in a transition course. Some students may need fur

ther explicit discussions of the structure of proofs. Such discussion appear

in many texts, such as

Chapter 6 Planar Graphs

Chapter 7 Edges and Cycles

* Total

Optional Material

No later material requires material marked optional. The optional

marking also suggests to students that the nal examination will not cover

that material.

The optional subsections on Disjoint Spanning Trees (BridgIt) in Sec

tion 2.1 and Stable Matchings in Section 3.2 are always quite popular with

the students. The planarity algorithm (without proof) in 6.2 is appealing

to students, as is the notion of embedding graphs on the torus through

Example 6.3.21. Our course usually includes these four items.

The discussion of f factors in Section 3.3 is also very instructive and

is covered when the class is proceeding on schedule. Other potential addi

tions include the applications of Menger's Theorem at 4.2.24 or 4.2.25.

Other items marked optional generally should not be covered in class.

D'Angelo and West, Mathematical Thinking: ProblemSolving and Proofs ;

Eisenberg, The Mathematical Method: A Transition to Advanced Mathematics ;

Fletcher/Patty, Foundations of Higher Mathematics ;

Galovich, Introduction to Mathematical Structures ;

Galovich, Doing Mathematics: An Introduction to Proofs and Problem Solving ;

Solow, How to Read and Do Proofs .

Additional text items not marked optional that can be skipped when

behind schedule:

1.1: 31, 35

1.2: 16, 2123

1.3: 24, 3132

1.4: 1, 4, 7, 2526

2.1: 8, 1416 2.2: 1319

2.3: 78

3.2: 4

4.1: 46

4.2: 2021

5.1: 11, 22(proof) 5.3: 1011, 16(proof)

6.1: 1820, 28 6.3: 910, 1315

7.2: 17

Solutions

Preface

Comments

There are several underlying themes in the course, and mentioning

these at appropriate moments helps establish continuity. These include

1) TONCAS (The Obvious Necessary Condition(s) are Also Sufcient).

2) Weak duality in dual maximation and minimization problems.

3) Proof techniques such as the use of extremality, the paradigm for induc

tive proofs of conditional statements, and the technique of transforming a

problem into a previously solved problem.

Students sometimes nd it strange that so many exercises concern

the Petersen graph. This is not so much because of the importance of the

Petersen graph itself, but rather because it is a small graph and yet has

complex enough structure to permit many interesting exercises to be asked.

just to state the result and give an example (the next edition will include

a purely inductive proof that uses only determinant expansion, not the

CauchyBinet Formula). Students nd the material on graceful labelings

enjoyable and illuminating; it doesn't take long, but also it isn't required.

The material on branchings should certaily be skipped in this course.

2.3: Many students have seen rooted trees in computer science and

nd ordinary trees unnatural; Kruskal's algorithm should clarify the dis

tinction. Many CS courses now cover the algorithms of Kruskal, Dijkstra,

and Huffman; here cover Kruskal and perhaps Dijkstra (many students

have seen the algorithm but not a proof of correctness), and skip Huffman.

Chapter 3.

3.1: Skip Dominating Sets, but present the rest of the section.

3.2: Students nd the Hungarian algorithm difcult; explicit examples

need to be worked along with the theoretical discussion of the equality

subgraph. Stable Matchings is very popular with students and should be

presented unless far behind in schedule. Skip Faster Bipartite Matching.

3.3: Present all of the subsection on Tutte's 1factor Theorem. The

material on f factors is intellectually beautiful and leads to one proof of

the ErdosGallai conditions, but it is not used again in the course and is an

aside. Skip everything on Edmonds' Blossom Algorithm: matching algo

rithms in general graphs are important algorithmically but would require

too much time in this course; this is recommended reading.

Chapter 1. In recent years, most students enter the course having

been exposed to proof techniques, so reviewing these in the rst ve sec

tions has become less necessary; remarks in class can emphasis techniques

as reminders. To minimize confusion, digraphs should not be mentioned

until section 1.4; students absorb the additional model more easily after

becoming comfortable with the rst.

1.1: p36 contain motivational examples as an overview of the course;

this discussion should not extend past the rst day no matter where it

ends (the denitions are later repeated where needed). The material on

the Petersen graph establishes its basic properties for use in later examples

and exercises.

1.2: The denitions of path and cycle are intended to be intuitive; one

shouldn't dwell on the heaviness of the notation for walks.

1.3: Although characterization of graphic sequences is a classical topic,

some reviewers have questioned its importance. Nevertheless, here is a

computation that students enjoy and can perform.

1.4: The examples are presented to motivate the model; these can be

skipped to save time. The de Bruijn graph is a classical application. It is

desirable to present it, but it takes a while to explain.

Chapter 4.

4.1: Students have trouble distinguishing k connected from connec

tivity k and bonds from edge cuts. Bonds are dual to cycles in the

matroidal sense; there are hints of this in exercises and in Chapter 7, but

the full duality cannot be explored before Chapter 8.

4.2: Students nd this section a bit difcult. The proof of 4.2.10 is

similar to that of 4.2.7, making it omittable, but the application in 4.2.14

is appealing. The details of 4.2.2021 can be skipped or treated lightly,

since the main issue is the local version of Menger's theorem. 4.2.2425 are

appealing applications that can be added; 4.2.5 (CSDR) is a fundamental

result but takes a fair amount of effort.

4.3: The material on network ow is quite easy but can take a long

time to present due to the overhead of dening new concepts. The basic

idea of 4.3.1315 should be presented without belaboring the details too

much. 4.3.16 is a more appealing application that perhaps makes the point

more effectively. Skip Supplies and Demands.

Chapter 2.

2.1: Characterization of trees is a good place to ask for input from the

class, both in listing properties and in proving equivalence.

2.2: The inductive proof for the Pr ufer correspondence seems to be

easier for most students to grasp than the full bijective proof; it also illus

trates the usual type of induction with trees. Most students in the class

have seen determinants, but most have considerable difculty understand

ing the proof of the Matrix Tree Theorem; given the time involved, it is best

vii

Solutions

Preface

viii

Chapter 5.

5.1: If time is short, the proof of 5.1.22 (Brooks' Theorem) can be merely

sketched.

5.2: Be sure to cover Tur an's Theorem. Presentation of Dirac's The

orem in 5.2.20 is valuable as an application of the Fan Lemma (Menger's

Theorem). The subsequent material has limited appeal to undergraduates.

5.3: The inclusionexclusion formula for the chromatic polynomial is

derived here (5.3.10) without using inclusionexclusion, making it accessi

ble to this class without prerequisite. However, this proof is difcult for

students to follow in favor of the simple inclusionexclusion proof, which

will be optional since that formula is not prerequisite for the course. Hence

this formula should be omitted unless students know inclusionexclusion.

Chordal graphs and perfect graphs are more important, but these can also

be treated lightly if short of time. Skip Counting Acyclic Orientations.

Characterization of Line Graphs, although if time and interest is plenti

ful the necessity of Krausz's condition can be explained.

7.2: Chv atal's theorem (7.2.13) is not as hard to present as it looks if

the instructor has the statement and proof clearly in mind. Nevertheless,

the proof is somewhat technical and can be skipped (the same can be said

of 7.2.17). More appealing is the Chv atalErdos Theorem (7.2.19), which

certainly should be presented. Skip Cycles in Directed Graphs.

7.3: The theorems of Tait and Grinberg make a nice culmination to

the required material of the course. Skip Snarks and Flows and Cycle

Covers. Nevertheless, these are lively topics that can be recommended for

advanced students.

Chapter 8. If time permits, material from the rst part of sections of

Chapter 8 can be presented to give the students a glimpse of other topics.

The best choices for conveying some understanding in a brief treatment are

Section 8.3 (Ramsey Theory or Sperner's Lemma) and Section 8.5 (Random

Graphs). Also possible are the Gossip Problem (or other items) from Sec

tion 8.4 and some of the optional material from earlier chapters. The rst

part of Section 8.1 (Perfect Graphs) may also be usable for this purpose if

perfect graphs have been discussed in Section 5.3. Sections 8.2 and 8.6 re

quire more investment in preliminary material and thus are less suitable

for giving a glimpse.

Chapter 6.

6.1: The technical denitions of objects in the plane should be treated

very lightly. It is better to be informal here, without writing out formal

denitions unless explicitly requested by students. Outerplanar graphs

are useful as a much easier class on which to solve problems (exercises!)

like those on planar graphs; 6.1820 are fundamental observations about

outerplanar graphs, but other items are more important if time is short.

6.1.28 (polyhedra) is an appealing application but can be skipped.

6.2: The preparatory material 6.2.47 on Kuratowski's Theorem can be

presented lightly, leaving the annoying details as reading; the subsequent

material on convex embedding of 3connected graphs is much more inter

esting. Presentation of the planarity algorithm is appealing but optional;

skip the proof that it works.

6.3: The four color problem is popular; for undergraduates, show the

aw in Kempe's proof (p271), but don't present the discharging rule un

less ahead of schedule. Students nd the concept of crossing number easy

to grasp, but the results are fairly difcult; try to go as far as the recur

sive quartic lower bound for the complete graph. The edge bound and its

geometric application are impressive but take too much time for under

graduates. The idea of embeddings on surfaces can be conveyed through

the examples in 6.3.21 on the torus. Interested students can be advised to

read the rest of this section.

Chapter 7.

7.1: The proof of Vizing's Theorem is one of the more difcult in the

course, but undergraduates can gain follow it when it is presented with

sufcient colored chalk. The proof can be skipped if short of time. Skip

Chapter 1: Fundamental Concepts

Section 1.1: What Is a Graph?

1.1.5. If every vertex of a graph G has degree 2, then G is a cycleFALSE.

Such a graph can be a disconnected graph with each component a cycle. (If

innite graphs are allowed, then the graph can be an innite path.)

1.FUNDAMENTAL CONCEPTS

1.1.6. The graph below decomposes into copies of

P 4 .

1.1. WHAT IS A GRAPH?

1.1.1. Complete bipartite graphs and complete graphs. The complete bipar

tite graph K m ; n is a complete graph if and only if m D n D 1 or f m ; n gDf 1 ; 0 g .

1.1.2. Adjacency matrices and incidence matrices for a 3vertex path.

1.1.7. A graph with more than six vertices of odd degree cannot be decom

posed into three paths. Every vertex of odd degree must be the endpoint

of some path in a decomposition into paths. Three paths have only six

endpoints.

0 1 1

1 0 0

0 1 0

1 0 1

0 1 0

0 0 1

1 1 0

1.1.8. Decompositions of a graph. The graph below decomposes into copies

of K 1;3 with centers at the marked vertices. It decomposes into bold and

solid copies of

P 4 as shown.

1 1

1 0

0 1

1 1

0 1

1 0

1 1

0 1

1 1

1 0

0 1

1 1

0 1

1 0

1 1

Adjacency matrices for a path and a cycle with six vertices.

0 1 0 0 0 1

1 0 1 0 0 0

0 1 0 1 0 0

0 0 1 0 1 0

0 0 0 1 0 1

1 0 0 0 1 0

1.1.9. A graph and its complement. With vertices labeled as shown, two

vertices are adjacent in the graph on the right if and only if they are not

adjacent in the graph on the left.

1.1.3. Adjacency matrix for

K m ; n .

1.1.4. G D H if and only if G D H . If f is an isomorphism from G to H ,

then f is a vertex bijection preserving adjacency and nonadjacency, and

hence f preserves nonadjacency and adjacency in G and is an isomor

phism from G to H . The same argument applies for the converse, since the

complement of G

is G .

1.1.10. The complement of a simple disconnected graph must be connected

TRUE. A disconnected graph G has vertices x ; y that do not belong to a

path. Hence x and y are adjacent in G . Furthermore, x and y have no com

mon neighbor in G , since that would yield a path connecting them. Hence

0 1 0 0 0 0

1 0 1 0 0 0

0 1 0 1 0 0

0 0 1 0 1 0

0 0 0 1 0 1

0 0 0 0 1 0

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: