COMP5940M Graph Theory: Structure and Algorithms
Graph Theory: Structure and Algorithms
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP5940M
Graph Theory: Structure and Algorithms
Coursework #2
Released Monday, March 6, 2023, at 8 a.m.
Due Friday, March 17, 2023, by 5 p.m.
In the following problems, all graphs are finite, simple, and non-null (i.e.
they have at least one vertex).
Any result (theorem, lemma, etc.) from the Lecture notes may be used
without proof, as long as it is clearly stated which result is being used.
1
Problem 1. [10 points] Let S be a clique cutset of a graph G, and let
C1, . . . , Ck be the connected components of G \ S. We define the blocks of
decomposition by a clique cutset S to be graphs Gi = G[V (Ci) ∪ S], for
i = 1, . . . , k.
Prove that a graph G is chordal if and only if the blocks of decomposition
by a clique cutset are chordal.
Problem 2. [10 points] A clique cutset S is an extreme clique cutset if some
block of decomposition by S has no clique cutset.
Prove that if a graph G has a clique cutset, then it has an extreme clique
cutset.
Problem 3. [10 points] Prove that chordal graphs are perfect (without
using the Strong Perfect Graph Theorem).
Hint: Use Theorem 4.2.