For a graph G, let ∂(G) denote the maximum number k such that G contains a circuit with k diagonals. Theorem. For any graph G with minimum valencyn≥ 3, ∂(G) ≥ 1 2 (n+1)(n-2). If the equality holds and G is connected, then either G is isomorphic to Kn+1 or G is separable and each of its terminal blocks is isomorphic to Kn+1, or Kn+1 with one edge subdivided.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics