Biconnectivity

Question 1

What is a cut-vertex? And a cut-set?

Answer 1

A cut vertex, v, meand G-v has more connected components than G. A cut set, S, means G-S is disconnected.

Question 2

When is a graph biconnected?

Answer 2

When it has at least 3 vertices, is connected and has no cut vertex, i.e. a cycle.

Question 3

For every biconnected graph G and for all u,v in V(G), there is a ___ in G through u and v

Answer 3

cycle

Question 4

What is a block H in the graph G? State 3 conditions

Answer 4

-H is a maximal biconnected subgraph of G (as in it is a subgraph of no other biconnected subgraph in G)
-H consists of a bride edge in G and its two end points
-H consists of an isolated vertex in G with no edges

Question 5

For every graph G, the blocks of G form a ___ ___ ___

Answer 5

Partition of E(G)

Question 6

For every graph G the chromatic number chi(G) equals the ___ ___ ___ of all the ___ ___ ___

Answer 6

the maximum chromatic number of all the blocks of G

Question 7

State Brook’s Colouring Theorem

Answer 7

Every graph G with maximum degree Delta is Delta-colourable, unless some component of G is the complete graph K_{Delta+1} or Delta=2 and some component of G is an odd cycle.

Question 8

If a graph G with max degree Delta contains 2 vertices u and v at distance ___ such that G-u-v is connected, then G is ___-___

Answer 8

2… Delta-colourable

Question 9

Let G be a biconnected graph that is not a complete graph or a cycle. Then G contains vertices u and v at distance ___ in G such that G-u-v is ___

Answer 9

2… connected