Question 4 Consider the graph G given by the following drawing. U6 U5 U4 Ա3 Աշ U1 VA V5 V6 V3 V₁ V2 (a) Determine whether G is bipartite. Show your working. (b) For each of the following sets, state whether it is a matching of G. Justify your answers. (i) {} (ii) {u2v2, U3V3, U4V4, U5V5} (iii) {u1u2, U3u4, V3 V4 V5 V6} Now consider the graph H given by the following drawing. x2 x3 x4 x5 X6 x1 Y1 Y2 Y3 Y4 Y5 Y6 (c) Find a maximum matching of H. Show your working. (d) Use Hall's theorem to show that H does not have a perfect matching.
Question 4 Consider the graph G given by the following drawing. U6 U5 U4 Ա3 Աշ U1 VA V5 V6 V3 V₁ V2 (a) Determine whether G is bipartite. Show your working. (b) For each of the following sets, state whether it is a matching of G. Justify your answers. (i) {} (ii) {u2v2, U3V3, U4V4, U5V5} (iii) {u1u2, U3u4, V3 V4 V5 V6} Now consider the graph H given by the following drawing. x2 x3 x4 x5 X6 x1 Y1 Y2 Y3 Y4 Y5 Y6 (c) Find a maximum matching of H. Show your working. (d) Use Hall's theorem to show that H does not have a perfect matching.
Chapter1: Equations, Inequalities, And Mathematical Modeling
Section1.1: Graphs Of Equations
Problem 6ECP: Use symmetry to sketch the graph of xy2=1.
Related questions
Question
Transcribed Image Text:Question 4
Consider the graph G given by the following drawing.
U6
U5
U4
Ա3
Աշ
U1
VA
V5
V6
V3
V₁
V2
(a) Determine whether G is bipartite. Show your working.
(b) For each of the following sets, state whether it is a matching of G. Justify your
answers.
(i) {}
(ii) {u2v2, U3V3, U4V4, U5V5}
(iii) {u1u2, U3u4, V3 V4 V5 V6}
Now consider the graph H given by the following drawing.
x2
x3
x4
x5
X6
x1
Y1
Y2
Y3
Y4
Y5
Y6
(c) Find a maximum matching of H. Show your working.
(d) Use Hall's theorem to show that H does not have a perfect matching.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps with 3 images
Recommended textbooks for you
Trigonometry (MindTap Course List)
Trigonometry
ISBN:
9781337278461
Author:
Ron Larson
Publisher:
Cengage Learning
Algebra & Trigonometry with Analytic Geometry
Algebra
ISBN:
9781133382119
Author:
Swokowski
Publisher:
Cengage
Trigonometry (MindTap Course List)
Trigonometry
ISBN:
9781337278461
Author:
Ron Larson
Publisher:
Cengage Learning
Algebra & Trigonometry with Analytic Geometry
Algebra
ISBN:
9781133382119
Author:
Swokowski
Publisher:
Cengage
College Algebra (MindTap Course List)
Algebra
ISBN:
9781305652231
Author:
R. David Gustafson, Jeff Hughes
Publisher:
Cengage Learning
Holt Mcdougal Larson Pre-algebra: Student Edition…
Algebra
ISBN:
9780547587776
Author:
HOLT MCDOUGAL
Publisher:
HOLT MCDOUGAL
