A characterisation of some 2-connected graphs and a comment on an algorithmic proof of Brooks' theorem

✍ Scribed by Victor Bryant

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 196 KB
• Volume: 158
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(95)00082-8

✦ Synopsis

A simple characterisation of cycles and complete graphs highlights their significance in Brooks' theorem. It then shows that an algorithmic proof of that theorem. usually dealt with in two cases. is in fact covered by one of the cases.

1. Some 2-connected graphs

Throughout this paper G = (V, E) is a simple 2-connected graph (i.e. it is connected and the removal of any one vertex leaves a connected graph). A q& y~uph is a connected graph in which each vertex has degree 2. The distunw between two vertices in a connected graph is the number of edges in any shortest path between them.

Proof. (i) + (ii) 3 (iii). Immediate.

(iii) + (i). Assume that (iii) holds and that G is not complete. Then we shall show that every vertex of G has degree 2.

Since G is 2-connected but not complete it certainly has no vertices of degree 0 or 1. Let $1' be a vertex of G of maximum degree d. Then we claim that there are two non-adjacent vertices, II and c say, adjacent to IV. For, if all the d vertices adjacent to M' were themselves mutually adjacent, then, as G is connected but not complete, one