MTH 607 Graph Theory Lab 7
For the graphs below:
G
1
G
2
G
3
Find all cut vertices.
Find all bridges
Find the blocks of the graphs.
Trace through the block finding algorithm and indicate the P value of each vertex, its parent and block.
(Book 5.12) If a graph contains 3 blocks and
k
cut vertices, what are the possible values of
k
?
Show that if a connected graph
G
with
k
blocks
B
1
. . .
B
k
then
n
(
G
) = [ Σ
k
i
=1
n
(
B
i
) ] -
k
+ 1
Where
n
(
X
) is the number of points in
X
.
Consider the statement P:
If
e
is a cut edge of a graph then one of the vertices of
e
is a cut vertex.
Give a counterexample to show that the P is false.
Think of a condition to add to this statement which would make P true.
Prove the amended statement.
The graph Q
3
below is both 3-connected and 3-edge connected.
Find three internally disjoint paths between
000 and 011;
000 and 101.
Find three edge disjoint disjoint paths between.
000 and 011;
000 and 101.
