Bridges of longest cycles (Q1262875)

This paper is concerned with the structure of the subgraph outside a longest cycle in a nonhamiltonian graph. Let C be a longest cycle in a graph G. A bridge of C is either a component of G-V(C) together with its attachments or a chord of C. A C-path is a path of G such that only its endvertices are on C. If B is a bridge of C, let P be a longest C-path contained in B. Then the length of the bridge B is defined to be the length of P. Theorem. Let G be a 3-connected nonhamiltonian graph and suppose \(d(x)+d(y)\geq m\) for each pair x, y of nonadjacent vertices of G. If the length of any longest cycle C is r then the length of any bridge of C is at most \(r-m+2\).