The number of blocks of a graph with given minimum degree (Q2657452)

Summary: A block of a graph is a nonseparable maximal subgraph of the graph. We denote by \(b\left( G\right)\) the number of block of a graph \(G\). We show that, for a connected graph \(G\) of order \(n\) with minimum degree \(k\geq1\), \(b\left( G\right)<\left( \left( 2 k - 3\right) / \left( k^2 - k - 1\right)\right)n\). The bound is asymptotically tight. In addition, for a connected cubic graph \(G\) of order \(n\geq14\), \(b\left( G\right)\leq\left( n / 2\right)-2\). The bound is tight.