第1页 / 共260页
第2页 / 共260页
第3页 / 共260页
第4页 / 共260页
第5页 / 共260页
第6页 / 共260页
第7页 / 共260页
第8页 / 共260页
Introduction to Graph Theory West 2e solutions 图论导引 第二版 West 答案.pdf
i
ii
INTRODUCTION TO GRAPH THEORY
NOTICE
SECOND EDITION (2001)
SOLUTION MANUAL
SUMMER 2005 VERSION
c DOUGLAS B. WEST
MATHEMATICS DEPARTMENT
UNIVERSITY OF ILLINOIS
All rights reserved. No part of this work may be reproduced
or transmitted in any form without permission.
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.
Douglas B. West
iii
Solutions
Preface
iv
Mathematics Department - University of Illinois
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
D’Angelo and West, Mathematical Thinking: Problem›Solving 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.
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 fty›minute lectures.
The nal two lectures are for optional topics, usually chosen by the students
from topics in Chapter 8.
Chapter 1 Fundamental Concepts
Chapter 2 Trees and Distance
Chapter 3 Matchings and Factors
Chapter 4 Connectivity and Paths
Chapter 5 Graph Coloring
Chapter 6 Planar Graphs
Chapter 7 Edges and Cycles
* Total
8
5.5
5.5
6
6
5
5
41
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 (Bridg›It) 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.
Additional text items not marked optional that can be skipped when
behind schedule:
1.1: 31, 35
2.1: 8, 1416
4.1: 46
6.1: 1820, 28 6.3: 910, 1315
1.2: 16, 2123
2.2: 1319
4.2: 2021
1.3: 24, 3132
2.3: 78
5.1: 11, 22(proof) 5.3: 1011, 16(proof)
1.4: 1, 4, 7, 2526
3.2: 4
7.2: 17
v
Solutions
Preface
vi
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.
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: p3›6 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 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
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
Cauchy›Binet 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 1›factor Theorem. The
material on f ›factors is intellectually beautiful and leads to one proof of
the Erdos›Gallai 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 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.20›21 can be skipped or treated lightly,
since the main issue is the local version of Menger’s theorem. 4.2.24›25 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.13›15 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.
vii
Solutions
Preface
viii
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 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 inclusion›exclusion formula for the chromatic polynomial is
derived here (5.3.10) without using inclusion›exclusion, making it accessi›
ble to this class without prerequisite. However, this proof is difcult for
students to follow in favor of the simple inclusion›exclusion proof, which
will be optional since that formula is not prerequisite for the course. Hence
this formula should be omitted unless students know inclusion›exclusion.
Chordal graphs and perfect graphs are more important, but these can also
be treated lightly if short of time. Skip Counting Acyclic Orientations.
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.18›20 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.4›7 on Kuratowski’s Theorem can be
presented lightly, leaving the annoying details as reading; the subsequent
material on convex embedding of 3›connected 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
1
Chapter 1: Fundamental Concepts
Section 1.1: What Is a Graph?
2
1.FUNDAMENTAL CONCEPTS
1.1. WHAT IS A GRAPH?
1.1.1. Complete bipartite graphs and complete graphs. The complete bipar›
tite graph Km;n is a complete graph if and only if m D n D 1 or fm; ng D f1; 0g.
1.1.2. Adjacency matrices and incidence matrices for a 3›vertex path.
1 0 0
1 0 1
0 1 0! 0 0 1
0 1 1
1 0 0! 0 1 0
1 1 0!
1 1! 0 1
1 0! 1 0
0 1! 0 1
1 0! 1 0
1 1
0 1! 1 1
1 1!
0 0 1
1 1
1 1
0 1
1 0
0 1
1 0
Adjacency matrices for a path and a cycle with six vertices.
0
BBBB@
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
1
CCCCA
0
BBBB@
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
CCCCA
1.1.3. Adjacency matrix for Km;n.
m
0
1
n
1
0
m
n
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.1.6. The graph below decomposes into copies of P4.
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.
1.1.8. Decompositions of a graph. The graph below decomposes into copies
of K1;3 with centers at the marked vertices. It decomposes into bold and
solid copies of P4 as shown.
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.
b
c
f
d
f
e
g
h
h
c
b
e
a
d
a
g
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 non›adjacency 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. Hencex 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
3
Chapter 1: Fundamental Concepts
Section 1.1: What Is a Graph?
4
every vertex not in fx ; yg is adjacent in G to at least one of fx ; yg. Hence
every vertex can reach every other vertex in G using paths through fx ; yg.
1.1.11. Maximum clique and maximum independent set. Since two ver›
tices have degree 3 and there are only four other vertices, there is no clique
of size 5. A complete subgraph with four vertices is shown in bold.
Since two vertices are adjacent to all others, an independent set con›
taining either of them has only one vertex. Deleting them leaves P4, in
which the maximum size of an independent set is two, as marked.
1.1.12. The Petersen graph. The Petersen graph contains odd cycles, so it
is not bipartite; for example, the vertices 12; 34; 51; 23; 45 form a 5›cycle.
The vertices 12; 13; 14; 15 form an independent set of size 4, since any
two of these vertices have 1 as a common element and hence are nonadja›
cent. Visually, there is an independent set of size 4 marked on the drawing
of the Petersen graph on the cover of the book. There are many ways to
show that the graph has no larger independent set.
Proof 1. Two consecutive vertices on a cycle cannot both appear in an
independent set, so every cycle contributes at most half its vertices. Since
the vertex set is covered by two disjoint 5›cycles, every independent set has
size at most 4.
Proof 2. Let ab be a vertex in an independent set S, where a; b 2 [5].
We show that S has at most three additional vertices. The vertices not
adjacent to ab are ac; bd; ae; bc; ad; be, and they form a cycle in that order.
Hence at most half of them can be added to S.
1.1.13. The graph with vertex set f0; 1gk and x $ y when x and y differ in
one place is bipartite. The partite sets are determined by the parity of the
number of 1’s. Adjacent vertices have opposite parity. (This graph is the
k›dimensional hypercube; see Section 1.3.)
1.1.14. Cutting opposite corner squares from an eight by eight checkerboard
leaves a subboard that cannot be partitioned into rectangles consisting of
two adjacent unit squares. 2›coloring the squares of a checkerboard so
that adjacent squares have opposite colors shows that the graph having
a vertex for each square and an edge for each pair of adjacent squares
is bipartite. The squares at opposite corners have the same color; when
these are deleted, there are 30 squares of that color and 32 of the other
color. Each pair of adjacent squares has one of each color, so the remaining
squares cannot be partitioned into sets of this type.
Generalization: the two partite sets of a bipartite graph cannot be
matched up using pairwise›disjoint edges if the two partite sets have un›
equal sizes.
1.1.15. Common graphs in four families: A D fpathsg, B D fcyclesg, C D
fcomplete graphsg, D D fbipartite graphsg.
A \ B D ?: In a cycle, the numbers of vertices and edges are equal,
but this is false for a path.
A \ C D fK1; K2g: To be a path, a graph must contain no cycle.
A \ D D A: non›bipartite graphs have odd cycles.
B \ C D K3: Only when n D 3 doesn
B \ D D fC2k: k 2g: odd cycles are not bipartite.
C \ D D fK1; K2g: bipartite graphs cannot have triangles.
2 D n.
1.1.16. The graphs below are not isomorphic. The graph on the left has four
cliques of size 4, and the graph on the right has only two. Alternatively, the
complement of the graph on the left is disconnected (two 4›cycles), while
the complement of the graph on the right is connected (one 8›cycle).
1.1.17. There are exactly two isomorphism classes of 4›regular simple
graphs with 7 vertices. Simple graphs G and H are isomorphic if and
only if their complements G and H are isomorphic, because an isomor›
phism : V .G/ ! V .H / is also an isomorphism from G to H, and vice
versa. Hence it sufces to count the isomorphism classes of 2›regular sim›
ple graphs with 7 vertices. Every component of a nite 2›regular graph is a
cycle. In a simple graph, each cycle has at least three vertices. Hence each
class it determined by partitioning 7 into integers of size at least 3 to be
the sizes of the cycles. The only two graphs that result are C7 and C3 C C4
a single cycle or two cycles of lengths three and four.
1.1.18. Isomorphism. Using the correspondence indicated below, the rst
two graphs are isomorphic; the graphs are bipartite, with ui $ vj if and
only if i 6D j. The third graph contains odd cycles and hence is not isomor›
phic to the others.
5
Chapter 1: Fundamental Concepts
Section 1.1: What Is a Graph?
6
u1
v2
v4
u2
u3 v1
v3
u4
u1
u2
u3
u4
v1
v2
v3
v4
Visually, the rst two graphs are Q3 and the graph obtained by delet›
ing four disjoint edges from K4;4. In Q3, each vertex is adjacent to the
vertices whose names have opposite parity of the number of 1s, except for
the complementary vertex. Hence Q3 also has the structure of K4;4 with
four disjoint edges deleted; this proves isomorphism without specifying an
explicit bijection.
1.1.19. Isomorphism of graphs. The rightmost two graphs below are iso›
morphic. The outside 10›cycle in the rightmost graph corresponds to the
intermediate ring in the second graph. Pulling one of the inner 5›cycles of
the rightmost graph out to the outside transforms the graph into the same
drawing as the second graph.
The graph on the left is bipartite, as shown by marking one partite set.
It cannot be isomorphic to the others, since they contain 5›cycles.
1.1.20. Among the graphs below, the rst (F) and third (H) are isomorphic,
and the middle graph (G) is not isomorphic to either of these.
F and H are isomorphic. We exhibit an isomorphism (a bijection from
V .F / to V .H / that preserves the adjacency relation). To do this, we name
the vertices of F, write the name of each vertex of F on the corresponding
vertex in H, and show that the names of the edges are the same in H and
F. This proves that H is a way to redraw F. We have done this below using
the rst eight letters and the rst eight natural numbers as names.
To prove quickly that the adjacency relation is preserved, observe that
1; a; 2; b; 3; c; 4; d; 5; e; 6; f; 7; g; 8; h is a cycle in both drawings, and the ad›
ditional edges 1c; 2d; 3e; 4 f; 5g; 6h; 7a; 8b are also the same in both draw›
ings. Thus the two graphs have the same edges under this vertex corre›
spondence. Equivalently, if we list the vertices in this specied order for
the two drawings, the two adjacency matrices are the same, but that is
harder to verify.
G is not isomorphic to F or to H. In F and in H, the numbers form an
independent set, as do the letters. Thus F and H are bipartite. The graph
G cannot be bipartite, since it contains an odd cycle. The vertices above
the horizontal axis of the picture induce a cycle of length 7.
It is also true that the middle graph contains a 4›cycle and the others
do not, but it is harder to prove the absence of a 4›cycle than to prove the
absence of an odd cycle.
3
4
c
b
6
e
1
h
d
5
a
2
f
g
8
7
h
8
g
7
f
6
1
a
2
b
3
c
4
d
5e
1.1.21. Isomorphism. Both graphs are bipartite, as shown below by mark›
ing one partite set. In the graph on the right, every vertex appears in
eight 4›cycles. In the graph on the left, every vertex appears in only six
4›cycles (it is enough just to check one). Thus they are not isomorphic.
Alternatively, for every vertex in the right graph there are ve vertices
having common neighbors with it, while in the left graph there are six
such vertices.
Isomorphism of explicit graphs.
1.1.22.
Among the graphs below,
fG1; G2; G5g are pairwise isomorphic. Also G3 D G4, and these are not
isomorphic to any of the others. Thus there are exactly two isomorphism
classes represented among these graphs.
To prove these statements, one can present explicit bijections between
vertex sets and verify that these preserve the adjacency relation (such as
by displaying the adjacency matrix, for example). One can also make other
structural arguments. For example, one can move the highest vertex in G 3
down into the middle of the picture to obtain G4; from this one can list the
desired bijection.
7
Chapter 1: Fundamental Concepts
Section 1.1: What Is a Graph?
8
One can also recall that two graphs are isomorphic if and only if their
complements are isomorphic. The complements of G 1, G2, and G5 are cy›
cles of length 7, which are pairwise isomorphic. Each of G 3 and G4 consists
of two components that are cycles of lengths 3 and 4; these graphs are
isomorphic to each other but not to a 7›cycle.
G1
G2
G3
G4
G5
1.1.23. Smallest pairs of nonisomorphic graphs with the same vertex de›
grees. For multigraphs, loopless multigraphs, and simple graphs, the re›
quired numbers of vertices are 2,4,5; constructions for the upper bounds
appear below. We must prove that these constructions are smallest.
different lists of vertex degrees (similarly for 4 edges). For 3 edges, the
three isomorphism classes have degree lists 3111, 2220, and 2211, all dif›
ferent. Hence nonisomorphic simple graphs with the same vertex degrees
must have at least ve vertices.
1.1.24. Isomorphisms for the Petersen graph. Isomorphism is proved by
giving an adjacency›preserving bijection between the vertex sets. For picto›
rial representations of graphs, this is equivalent to labeling the two graphs
with the same vertex labels so that the adjacency relation is the same
in both pictures; the labels correspond to a permutation of the rows and
columns of the adjacency matrices to make them identical. The various
drawings of the Petersen graph below illustrate its symmetries; the label›
ings indicate that these are all the same (unlabeled) graph. The number
of isomorphisms from one graph to another is the same as the number of
isomorphisms from the graph to itself.
a) general b) loopless
c) simple
a) With 1 vertex, every edge is a loop, and the isomorphism class is
determined by the number of edges, which is determined by the vertex
degree. Hence nonisomorphic graphs with the same vertex degrees have
at least two vertices.
b) Every loopless graph is a graph, so the answer for loopless graphs
is at least 2. The isomorphism class of a loopless graph with two vertices
is determined by the number of copies of the edge, which is determined
by the vertex degrees. The isomorphism class of a loopless graph with
three vertices is determined by the edge multiplicities. Let the three vertex
degrees be a; b; c, and let the multiplicities of the opposite edges be x ; y; z,
where Since a D y C z, b D x C z, and c D x C y, we can solve for the
multiplicities in terms of the degrees by x D .b C c a/=2, y D .a C c b/=2,
and z D .a C b c/=2. Hence the multiplicities are determined by the
degrees, and all loopless graphs with vertex degrees a; b; c are pairwise
isomorphic. Hence nonisomorphic loopless graphs with the same vertex
degrees have at least four vertices.
c) Since a simple graph is a loopless graph, the answer for simple
graphs is at least 4. There are 11 isomorphism classes of simple graphs
with four vertices. For each of 0,1,5, or 6 edges, there is only one isomor›
phism class. For 2 edges, there are two isomorphism classes, but they have
35
24
23
41
35
45
12
12
51
13
34
51
13
52
24
34
35
41
24
51
41
52
23
13
45
23
34
12
52
45
35
12
45
23
41
34
52
13
51
24
1.1.25. The Petersen graph has no cycle of length 7. Suppose that the Pe›
tersen graph has a cycle C of length 7. Since any two vertices of C are
connected by a path of length at most 3 on C, any additional edge with
endpoints on C would create a cycle of length at most 4. Hence the third
neighbor of each vertex on C is not on C.
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
