[go: up one dir, main page]
Scribd
Upload
10 views1 page

Solutions 8

This document provides guidelines for solving problems in graph theory, specifically focusing on cut vertices and matching decompositions. It discusses the implications of Kőnig’s theorem and Vizing’s theorem in relation to the properties of graph components and matchings. The solutions illustrate how to manipulate matchings to achieve a desired structure within the graph.

Uploaded by

Anuj Jha
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
10 views1 page

Solutions 8

This document provides guidelines for solving problems in graph theory, specifically focusing on cut vertices and matching decompositions. It discusses the implications of Kőnig’s theorem and Vizing’s theorem in relation to the properties of graph components and matchings. The solutions illustrate how to manipulate matchings to achieve a desired structure within the graph.

Uploaded by

Anuj Jha
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

Graph Theory

Solutions 8

The purpose of this write-up is merely to provide some guideline on how solutions should
look like, and to help clean up hazy arguments. For hints for other problems, feel free to consult
your teaching assistant.

Problem 4:
Suppose u is a cut vertex and let v, w be two vertices adjacent to v, but in different blocks
of G. By Kőnig’s theorem, the edge set of G splits into perfect matchings, let Mv be the one
containing uv and Mw be the one containing uw. Now look at G0 = G − u, and let Gv be the
component of v in it. Mv − uv is a matching in G0 that covers everything but v. This means
that Gv contains an odd number of vertices. On the other hand, Mw − uw is a matching in
G0 that covers everything but w, in particular, all the vertices in Gv . Hence Gv has an even
number of vertices. This contradiction shows that the graph contains no cut vertex, i.e. it is
2-connected.

Problem 5:
By Vizing’s theorem, the edge set of G can be partitioned into d = ∆ + 1 matchings
M1 , . . . , Md (one of them might be the empty matching). We will show that if for some i
and j the sizes of Mi and Mj are at least two apart, say e(Mi ) ≥ e(Mj ) + 2, then we can
rearrange the edges of Mi ∪ Mj into two matchings Mi0 and Mj0 such that e(Mi0 ) = e(Mi ) − 1
and e(Mj0 ) = e(Mj ) + 1. This is enough, because e.g. e(Ml )2 will decrease, so repeating this
P

operation, we will eventually arrive at a matching decomposition, where the sizes are at most
one apart (so their value is either be/dc or de/de.
To prove this, look at Mi ∪ Mj : it is a union of alternating cycles and paths. Since Mi has
more edges than Mj , there must be a path that starts and ends with an edge from Mi . Flipping
the edges along this path decreases the number of edges in Mi by 1 and increases the number
in Mj by 1, and of course the new Mi and Mj are still matchings. So we can choose them to
be Mi0 and Mj0 above.

You might also like