# The Number of Blocks of a Graph with Given Minimum Degree

Authors: Lei Li; Baoyindureng Wu
Journal: Discrete Dynamics in Nature and Society
 (2021)

---

## Abstract

A block of a graph is a nonseparable maximal subgraph of the graph. We denote bybG the number of block of a graph G. We show that, for a connected graph G of order n with minimum degree k≥1, bG<2k−3/k2−k−1n. The bound is asymptotically tight. In addition, for a connected cubic graph G of order n≥14, bG≤n/2−2. The bound is tight.


---

## Body

## 1. Introduction

We consider finite, undirected, simple graphs only. LetG=VG,EG be a graph. The numbers of vertices and edges of G are called the order and the size of G and denoted by vG and eG, respectively. A vertex v is called a cut vertex if comG−v>comG, where comG denotes the number of components of G. cG denotes the number of cut vertices of G. Rao [1] proved that, for a connected graph G of order n and size m,(1)cG≤maxq:m≤n−q2+q,characterized all extremal graphs. Rao and Rao [2] solved the corresponding problem for a strong digraph. Later, Achuthan and Rao [3] determined the maximum number of cut edges in a connected d-regular graph of order p.Letfn,d=maxcG:G is a connected k-regular graph of order n. Rao [4] determined fn,d for d≤4. Nirmala and Rao [5] showed that fn,d=2n−d−5/d+1−1 or 2n−d−5/d+1−2 for odd d≥5 and have obtained an upper bound for fn,d for even d≥6.Alberten and Berman [6] proved that, for a graph G of order n and minimum degree k≥2,(2)cG<2k−2k2−2n.This bound is asymptotically tight.Hopkins and Staton [7] showed that every connected graph of order n contains no more than r/2r−2n cut vertices of degree r. Some related results are referred to [8, 9].Aseparation of a connected graph is a decomposition of the graph into two nonempty connected subgraphs which have just one vertex in common. The common vertex is called a separating vertex of the graph. Since the graph G under consideration is simple, v∈VG is a separating vertex if and only if it is a cut vertex. A block of a graph is a nonseparable maximal subgraph of the graph. We denote by bG the number of blocks of a graph G.It is clear that any two blocks of a graph have at most one vertex in common. Recall that the block treeBG of G is the bipartite graph with bipartition B,S, where B is the set of blocks of G and S, the set of separating vertices of G, and a block B, and a separating vertex v is joined by an edge in BG if and only if B contains v. It is easy to see that if G is connected, BG is a tree. Each leaf of BG corresponds to an end block of G.Inspired from the bound for the cut vertices, in the present paper, we consider the upper bound for the number of blocks, a connected graph of ordern with given minimum degree. Let us begin with two easy cases when δG=1 and δG=2.Proposition 1.
For a connected graphG of order n≥2, bG≤n−1, with equality if and only if G is a tree.Proof.
Our proof is induction onn. If n=2, then G≅K2; thus, the result holds. Next, we assume that n≥3. If G has no cut vertex, then bG=1<n−1. Now suppose G has a cut vertex. Let B be an end block of G and v be the cut vertex, which belongs to B. Let G′=G−VB,v. Clearly, G′ is connected. By the induction hypothesis, bG′≤vG′−1. Since bG=bG′+1, vG′≤vG−1, we have bG≤n−1, with equality only if bG′=vG′−1=n−2 and B≅K2. By the induction hypothesis, G′ is a tree, implying that G is a tree.
On the contrary, ifG is a tree, clearly, bG=n−1.Proposition 2.
For a connected graphG of order n≥4 with δG≥2, bG≤n−3, with equality if and only if G is the graph obtained from Pn−4 identifying each end with a vertex of separate K3, as given in Figure 1.Figure 1
The extremal graph attaining the upper bound in Proposition2.Proof.
IfG has no cut vertex, the result holds trivially. Next, we assume that G has cut vertices, and thus, it has at least two end blocks and n≥5. Let B1,…,Bt be all end blocks of G. Let ci be the cut vertex of G, which belongs to Bi for each i∈1,…,t. Clearly, vBi≥3 for any i. If ci=cj for any two distinct i,j, then bG=t and n=∑i=1tvBi−1+1≥2t+1. Therefore, bG≤n−1/2≤n−3.
Otherwise,G has at least two cut vertices. It follows that the order n′ of G′=G−∪i=1tVBi,ci is at least two. Hence, n≥n′+2t and bG=bG′+t. By Proposition 1, bG′≤n′−1. Summing up the above, we have(3)bG=bG′+t≤n′−1+t≤n−t−1≤n−3.
From the above,bG=n−3 if and only if t=2 and G′=Pn−4, B1≅K3≅B2, as we promised.It is clear that, for a graphG of order n, bG decreases when δG increases. For a connected graph G of order n and minimum degree at least k, we have the following result, which is asymptotically best possible.Theorem 1.
For a connected graphG of order n with δG≥k, bG<2k−3/k2−k−1n.We show that the bound in the above theorem is asymptotically best possible. Letk≥3. Consider a tree T of order p with each vertex having degree k or 1. By the handshaking lemma, the number of leaves of this tree is(4)k−2p+2k−1.LetG be the graph obtained from identifying each leaf of T with a vertex of a clique of order k+1 separately. Therefore,(5)vG=p+k−2p+2k−1k,bG=p−1+k−2p+2k−1.So, we have(6)bGvG=2k−3p−k+3k2−k−1p+2k<2k−3k2−k−1.However, as p gets larger, bG/vG gets arbitrarily close to 2k−3/k2−k−1.What happens for thek-regular graphs? The situation becomes complicated. We are just able to get an exact bound for a cubic graph G of order n: bG<n/2 (Theorem 2), whereas by Theorem 1, we have bG<3/5n for a connected graph G of order n with δG≥3.Theorem 2.
For a connected cubic graphG of order n,(7)bG≤1,ifn≤8,3,ifn=12,n2−2,otherwise.The bound is sharp.To see the sharpness of the bound, we denote byK4∗ the graph obtained from K4 by replacing an edge with a path of length two, as drawn in Figure 2.Figure 2
K4∗.The graphsGn achieve the upper bound in Theorem 2, which are classified into three types in terms of n≡4 (mod 6), n≡0 (mod 6), and n≡2 (mod 6), respectively.For an integern≡4 (mod 6), k=n−4/3 is an even integer. Let Tk be a tree in which every vertex has degree 1 or 3. It is clear that Tk has exactly k+1/2 vertices of degree 1 (leaves) and k−1/2 vertices of degree 3. Let Gn be a graph obtained from identifying each leaf of Tk with the vertex of degree two of a separate K4∗, as shown in Figure 3.Figure 3
The extremal graphG of order n attaining the upper bound in Theorem 2, where (a) n≡4, (b) n≡0, and (c) n≡2 (mod 6), respectively.
(a)(b)(c)For an integern≡0 (mod 6), let Gn be a cubic graph obtained from a graph Gn−2 by replacing a vertex of degree three (not belongs to any K4∗) with a triangle, as shown in Figure 3.For an integern≡2 (mod 6), let Gn be a cubic graph obtained from a graph Gn−4 by inserting a K4−e into an edge of Gn−4 (not belongs to any K4∗), as shown in Figure 3.It can be checked thatvGn=n and bGn=n/2−2 for any graph Gn constructed as above.


## 2. The Proof of Theorem 1

Suppose the result is not true and letG be a counterexample of minimum order n, i.e., δG≥k and bG≥2k−3/k2−k−1n, but for any connected graph G′ of order n′<n with δG′≥k, bG′<2k−3/k2−k−1n′.Ifk∈1,2, 2k−3/k2−k−1n=n. By Propositions 1 and 2, bG≤n−1<n. Hence, k≥3. Since n≥k+1, we have 2k−3/k2−k−1n≥1, and thus, G has at least two blocks.Claim 1.
Every end block ofG is a clique of order k+1.Proof.
of Claim1. If it is not, let B be an end block of G. Let G′ be the graph obtained from G by replacing B with B′ of order k+1. Clearly, bG=bG′ and δG′≥k. By the choice of G,(8)bG′<2k−3k2−k−1n′.
Combining the above facts, we conclude thatbG<2k−3/k2−k−1n, contradicting the choice of G.Claim 2.
No cut vertex ofG belongs to at least two end blocks of G.Proof.
of Claim2. Let B and B′ be two end blocks of G containing the same cut vertex v of G. Let G′=G−VB′,v. By Claim 1, vB=vB′=k+1, and thus, vG′=n−k and δG′≥k. By the minimality of G,(9)bG′<2k−3k2−k−1n−k.Combining (9) with the fact that bG=bG′+1, we have a contradiction:(10)bG<2k−3k2−k−1n−k+1<2k−3k2−k−1n,Claim 3.
Letc be a cut vertex lying on an end block Bc. If B≠Bc is a block containing c, then B≅K2.Proof.
of Claim3. It suffices to show that vB=2.
First suppose thatvB≥k+1. Let G′ be the graph obtained from G,VBc,c and joining c to every vertex in VB,c. Clearly, G′ is a connected graph with δG′≥k. Moreover, by Claim 1, vG′=n−k. Again, by the minimality of G,(11)bG′<2k−3k2−k−1n−k.Combining (11) with the fact that bG=bG′+1, we have a contradiction.(12)bG<2k−3k2−k−1n−k+1<2k−3k2−k−1n,
Now assume thatvB∈3,…,k. Let VB=v1,…,vr, where v1=c. Since δG≥k and r≤k, each vi is a cut vertex of G. Let G′ be the graph obtained from G by identifying all vertices in v2,…,vr. Clearly, δG′≥k, n′<n, and bG′=bG. By the choice of G, bG′<2k−3/k2−k−1n′. Thus,(13)bG<2k−3k2−k−1n,contradicting the choice of G. This proves the claim.
Take a longest pathP of BG. Let B1 be an end block of G, which corresponds to a terminal vertex of P=B1c1B2c2B3c3⋯, where c1 be the unique cut vertex of G which belongs to B1. By Claim 3, B2≅K2. Next, we consider three possible cases in terms of the order vB3 of B3.


### 2.1. Case 1:vB3≥k+1

LetG′ be the graph obtained from G,VB1 and joining c2 to each vertex of VB3. It is clear that δG′≥k, and by Claim 1, vG′=n−k−1. By the minimality of G, bG′<2k−3/k2−k−1n−k−1. Since bG=bG′+2, we have(14)bG<2k−3k2−k−1n−k−1+2<2k−3k2−k−1n.


### 2.2. Case 2:vB3=2

By the choice ofP, each block B∗≠B3 of G containing c2 is isomorphic to K2. In addition, the end block containing the other end of B∗ is a leaf of BG. Since dc2≥k, there are k−1 such end block B1∗,…,Bk−1∗, each of which are jointed c2 with an edge. Let G′ be the graph obtained from G−∪i=1k−1VBi∗ by identifying a vertex of a new clique of order k+1 with c2. It is clear that δG′≥k, n′=vG′=n−k−1k+1+k, and bG′=bG−2k−1+1. So,(15)bG=bG′+2k−1−1<2k−3k2−k−1n′+2k−1−1=2k−3k2−k−1n−k−1k+1+k+2k−1−1=2k−3k2−k−1nis a contradiction.


### 2.3. Case 3:3≤vB3≤k

SinceδG≥k, each vertex of B3 is a cut vertex of G. We distinguish two subcases in terms of vB3.


#### 2.3.1. Case 3.1:vB3=k

SinceδG≥k, every vertex v∈VB3 has a neighbor not in VB3, which belongs to distinct blocks of G. Let G′ be the graph obtained from G by contracting B3 to a vertex v′. It can be seen that δG′≥k, bG=bG′+1, and n′=n−k+1. So,(16)bG=bG′+1<2k−3k2−k−1n−k+1+1<2k−3k2−k−1n.


#### 2.3.2. Case 3.2:3≤vB3≤k−1

Lets=vB3 and VB3=u1,…,us, where u1=c2 and us=c3. Since δG≥k, for any i∈1,…,s−1, there are at least k−s+1 blocks containing ui, each of which is isomorphic to K2, as illustrated in Figure 4.Figure 4
(a)G and (b) G′ in case 3.2.
(a)(b)LetG′ be the graph obtained from joining each component of G−u2,…,us−1 to c2 or c3 such that dG′cj≥k for each j∈2,3. In addition, add an edge c2c3 if c2c3∉EG. Note that G′ is a connected graph of order n′<n with δG′≥k and bG′=bG. By the minimality of G, bG′<2k−3/k2−k−1n′. Therefore, bG<2k−3/k2−k−1n, contradicting the choice of G.The proof of Theorem1 is completed.


## 2.1. Case 1:vB3≥k+1

LetG′ be the graph obtained from G,VB1 and joining c2 to each vertex of VB3. It is clear that δG′≥k, and by Claim 1, vG′=n−k−1. By the minimality of G, bG′<2k−3/k2−k−1n−k−1. Since bG=bG′+2, we have(14)bG<2k−3k2−k−1n−k−1+2<2k−3k2−k−1n.


## 2.2. Case 2:vB3=2

By the choice ofP, each block B∗≠B3 of G containing c2 is isomorphic to K2. In addition, the end block containing the other end of B∗ is a leaf of BG. Since dc2≥k, there are k−1 such end block B1∗,…,Bk−1∗, each of which are jointed c2 with an edge. Let G′ be the graph obtained from G−∪i=1k−1VBi∗ by identifying a vertex of a new clique of order k+1 with c2. It is clear that δG′≥k, n′=vG′=n−k−1k+1+k, and bG′=bG−2k−1+1. So,(15)bG=bG′+2k−1−1<2k−3k2−k−1n′+2k−1−1=2k−3k2−k−1n−k−1k+1+k+2k−1−1=2k−3k2−k−1nis a contradiction.


## 2.3. Case 3:3≤vB3≤k

SinceδG≥k, each vertex of B3 is a cut vertex of G. We distinguish two subcases in terms of vB3.


### 2.3.1. Case 3.1:vB3=k

SinceδG≥k, every vertex v∈VB3 has a neighbor not in VB3, which belongs to distinct blocks of G. Let G′ be the graph obtained from G by contracting B3 to a vertex v′. It can be seen that δG′≥k, bG=bG′+1, and n′=n−k+1. So,(16)bG=bG′+1<2k−3k2−k−1n−k+1+1<2k−3k2−k−1n.


### 2.3.2. Case 3.2:3≤vB3≤k−1

Lets=vB3 and VB3=u1,…,us, where u1=c2 and us=c3. Since δG≥k, for any i∈1,…,s−1, there are at least k−s+1 blocks containing ui, each of which is isomorphic to K2, as illustrated in Figure 4.Figure 4
(a)G and (b) G′ in case 3.2.
(a)(b)LetG′ be the graph obtained from joining each component of G−u2,…,us−1 to c2 or c3 such that dG′cj≥k for each j∈2,3. In addition, add an edge c2c3 if c2c3∉EG. Note that G′ is a connected graph of order n′<n with δG′≥k and bG′=bG. By the minimality of G, bG′<2k−3/k2−k−1n′. Therefore, bG<2k−3/k2−k−1n, contradicting the choice of G.The proof of Theorem1 is completed.


## 2.3.1. Case 3.1:vB3=k

SinceδG≥k, every vertex v∈VB3 has a neighbor not in VB3, which belongs to distinct blocks of G. Let G′ be the graph obtained from G by contracting B3 to a vertex v′. It can be seen that δG′≥k, bG=bG′+1, and n′=n−k+1. So,(16)bG=bG′+1<2k−3k2−k−1n−k+1+1<2k−3k2−k−1n.


## 2.3.2. Case 3.2:3≤vB3≤k−1

Lets=vB3 and VB3=u1,…,us, where u1=c2 and us=c3. Since δG≥k, for any i∈1,…,s−1, there are at least k−s+1 blocks containing ui, each of which is isomorphic to K2, as illustrated in Figure 4.Figure 4
(a)G and (b) G′ in case 3.2.
(a)(b)LetG′ be the graph obtained from joining each component of G−u2,…,us−1 to c2 or c3 such that dG′cj≥k for each j∈2,3. In addition, add an edge c2c3 if c2c3∉EG. Note that G′ is a connected graph of order n′<n with δG′≥k and bG′=bG. By the minimality of G, bG′<2k−3/k2−k−1n′. Therefore, bG<2k−3/k2−k−1n, contradicting the choice of G.The proof of Theorem1 is completed.


## 3. Proof of Theorem 2

Suppose the result is not true and letG be a counterexample of minimum order n. The following fact is clear:(1)
G must contain cut vertex.Since no cubic graph of order≤8 has a cut vertex, n≥10.(2)
Moreover,n≥14. If 10≤n≤12, it is not hard to check that bG≤3.Claim 4.
Every end block ofG is a K4∗.Proof.
of Claim4. If it is not, let B be an end block of G. Let G′ be the graph obtained from G by replacing B with K4∗. Clearly, G′ is a connected cubic graph of order n′<n and bG′=bG. By the minimality of G,(17)bG′≤n′2−2.
Combining the above facts, we conclude thatbG≤n/2−2, contradicting the choice of G.
Take a longest pathP of BG. Let B1 be an end block of G, which corresponds to a terminal vertex of P=B1c1B2c2B3c3⋯, where c1 be the unique cut vertex of G which belongs to B1. Since G is a cubic graph, B2≅K2. Next we consider three possible cases.


### 3.1. Case 1:vB3=k≥4

Ifv∈VB3 is a cut vertex of G, then v belongs to another block which is isomorphic to K2. In addition, the end block containing the other end of the K2 is a leaf of BG. We may assume B3 has r cut vertices except c3, which belong to B1′,B2′,…,Br′, respectively, where B1′=B1.LetG′ be the graph obtained from G−∪i=1rVBi′−VB3,c3 by identifying c3 with the vertex of degree two of a new K4∗. It is clear that G′ is a cubic graph of order n′=n−5r−k+5 and bG′=bG−2r. By the induction hypothesis, bG′≤1/2n−5r−k+5−2. Thus,(18)bG=bG′+2r≤12n−5r−k+5−2+2r=n2−r2−k2+12,k≥4,≤n2−2+12−r2≤n2−2.


### 3.2. Case 2:vB3=3

It follows thatB3≅K3. Every vertex of B3 is cut vertex. Let G′ be the graph obtained by the same operation as in the proof of Case 1. We have n′=n−8 and bG′=bG−4. Therefore,(19)bG=bG′+4≤12n−8−2+4=12n−2.


### 3.3. Case 3:vB3=2

By the choice ofP and vB3=2, one can find another longest path P′=B1′c1′B2′c2B3c3⋯ of BG. Let G′ be the graph obtained from identifying c2 of G−VB1−VB1′ with the vertex of degree two of a new K4∗. Note that bG′=bG−3 and n′=n−6. By the induction hypothesis, bG′≤n′/2−2. Therefore,(20)bG=bG′+3≤12n−6−2+3=12n−2.The proof is completed.


## 3.1. Case 1:vB3=k≥4

Ifv∈VB3 is a cut vertex of G, then v belongs to another block which is isomorphic to K2. In addition, the end block containing the other end of the K2 is a leaf of BG. We may assume B3 has r cut vertices except c3, which belong to B1′,B2′,…,Br′, respectively, where B1′=B1.LetG′ be the graph obtained from G−∪i=1rVBi′−VB3,c3 by identifying c3 with the vertex of degree two of a new K4∗. It is clear that G′ is a cubic graph of order n′=n−5r−k+5 and bG′=bG−2r. By the induction hypothesis, bG′≤1/2n−5r−k+5−2. Thus,(18)bG=bG′+2r≤12n−5r−k+5−2+2r=n2−r2−k2+12,k≥4,≤n2−2+12−r2≤n2−2.


## 3.2. Case 2:vB3=3

It follows thatB3≅K3. Every vertex of B3 is cut vertex. Let G′ be the graph obtained by the same operation as in the proof of Case 1. We have n′=n−8 and bG′=bG−4. Therefore,(19)bG=bG′+4≤12n−8−2+4=12n−2.


## 3.3. Case 3:vB3=2

By the choice ofP and vB3=2, one can find another longest path P′=B1′c1′B2′c2B3c3⋯ of BG. Let G′ be the graph obtained from identifying c2 of G−VB1−VB1′ with the vertex of degree two of a new K4∗. Note that bG′=bG−3 and n′=n−6. By the induction hypothesis, bG′≤n′/2−2. Therefore,(20)bG=bG′+3≤12n−6−2+3=12n−2.The proof is completed.


## 4. Conclusions and Future Work

By arguing the properties of a minimum counterexample to the assertion of the main theorems and by using several kinds of graph transformation, we arrive at a contradiction, and thereby, we show our results. However, the upper bound forbG remains open if G is a k-regular graph with k≥4. One of the referees pointed out the possibility of the obtained results to some real-life applications and other fields (see [10–12] for instance).



---

*Source: 6691960-2021-01-25.xml*