# Upper Bounds on the Diameter of Bipartite and Triangle-Free Graphs with Prescribed Edge Connectivity

Authors: Blessings T. Fundikwa; Jaya P. Mazorodze; Simon Mukwembi
Journal: International Journal of Mathematics and Mathematical Sciences
 (2020)

---

## Abstract

We present upper bounds on the diameter of bipartite and triangle-free graphs with prescribed edge connectivity with respect to order and size. All bounds presented in this paper are asymptotically sharp.


---

## Body

## 1. Introduction

Graph theory is used to study the mathematical structures of pairwise relations among objects. Mathematically, a pairG=V,E is a crisp graph, where V is a nonempty set and E is a relation on V [1]. The order of a graph G is the number of vertices of G and is denoted by V=n. The size of G, denoted by E=m, is the number of edges of G. The distance, dGu,v, between two vertices u,v of G is the length of a shortest u-v path in G. The eccentricity, ecGv, of a vertex v∈V is the maximum distance between v and any other vertex in G. The maximum distance among all pairs of vertices [2], also known as the value of the maximum eccentricity of the vertices of G, is called the diameter of G denoted by diamG. The degree, degv, of a vertex v of G is the number of edges incident with v. The minimum degree, δG=δ, of G is the minimum of the degrees of vertices in G. The open neighborhood, Nv, of a vertex v is simply the set containing all the vertices adjacent to v. The closed neighborhood, Nv, of a vertex v is simply the set containing the vertex v itself and all the vertices adjacent to v. We denote by EV1,V2 the set e=xyx∈V1,y∈V2 of edges with one end in V1 and the other end in V2. The edge connectivity, λG=λ, of G is the minimum number of edges whose deletion from G results in a disconnected or trivial graph. A complete graph, Kn, is a graph in which every vertex is adjacent to every other vertex. The most likely antonym for a complete graph is a null graph, Nn, which is a graph containing only vertices and no edges. A bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets U and V such that every edge in G connects a vertex in U to a vertex in V; furthermore, no two vertices in the same set are adjacent to each other. A graph is triangle-free if it does not contain C3 as a subgraph and C4-free if it does not contain C4 as a subgraph. It is important to observe from the above definitions that every bipartite graph is triangle free, but there are some triangle-free graphs which are not bipartite, for example, a cycle graph with five vertices C5. For notions not defined here, we refer the reader to [3].Our motivation for this paper comes from the results published by Erdős et al. in [4] and Mukwembi in [5].Graphs with forbidden subgraphs are a big part of graph theory literature such as in [4–8]. All graphs in this paper forbid cycle C3 as a subgraph. In this paper, we are concerned, in part, with upper bounds on the diameter of bipartite and triangle-free graphs with prescribed edge connectivity in terms of order. The diameter is the most common of the classical distance parameters in graph theory, and much of the research on distances is in fact on the diameter [9]. Several upper bounds on diameter in terms of order and other graph parameters are known, and we list a few relevant results below. A well-known and easy to recall result is 1≤diamG≤n−1. Needless to say, this bound is not only tight for ordinary graphs but also for the field of vision of this paper whenever λ=1 with the extremal graph being any path, Pn, on n vertices. Erdős et al. [4] found out that if G is a connected graph of order n and minimum degree δ≥2, then(1)diamG≤3nδ+1−1,and they also constructed graphs that, apart from the additive constant, attain the bound. They went further in the same paper and investigated triangle-free and C4-free graphs proving that if G is a connected triangle-free graph of order n and minimum degree δ≥2, then(2)diamG≤4n−δ−12δ.This can be rewritten as(3)diamG≤2nδ+1.In the same paper, they asserted that ifG is a connected C4-free graph of order n and minimum degree δ≥2, then(4)diamG≤5nδ2−2δ/2+1.Mukwembi [5] investigated λ-edge-connected graphs and discovered, amongst other bounds, that if G is a λ-edge-connected graph of order n, then(5)diamG≤3nλ+1−1.Letx,y∈V be fixed vertices in G such that dx,y=diamG=d and let Ni=v∈VdGx,v=i for any 0≤i≤d and ki=Ni. The following observation by Mukwembi [5] is essential to this paper.


### 1.1. Observation

LetG be a λ-edge-connected graph, V1,V2⊂V with V1∩V2=∅. Clearly, EV1,V2≤V1V2. If EV1,V2 is a disconnecting set of G, then EV1,V2≥λG so that V1V2≥λG. Let v∈V. Note also that for i=0,1,…,ecGv−1, it is clear that ENi,Ni+1 is a disconnecting set of G.The following fact follows from the above observation.Fact 1.
kiki+1≥λ for all i=1,2,…,ecGv−1.
The following useful facts follow from the well-known AM-GM inequalityab≤a+b/22. That is to say, the geometric mean of two (positive) real numbers never exceeds their arithmetic mean.Fact 2.
For positive integersa and b, if ab≥2, then a+b≥3.Fact 3.
For positive integersa and b, if ab≥5, then a+b≥5.
It is the purpose of this paper to bound the diameter of any triangle-free graph with respect to order and edge connectivity. We have dealt with the case whereinλ=1 and we now proceed to higher values of the same.Theorem 1.
LetG be a triangle-free graph of order n and diameter d≥1. If λ=2, then(6)diamG≤2n3−1.
Further, this inequality is best possible.Proof.
Note that sinceG is 2-edge-connected by the condition of the lemma, we have kiki+1≥2 from Fact 1. From this and Fact 2, we have ki+ki+1≥3. Thus, we have two cases.Case 1. d is even.(7)n=∑i=0dki=∑i=0d−2/2k2i+k2i+1+kd≥∑i=0d−2/23+1=3d2+1,and makingd subject of the formula, we obtain d≤2n/3−2/3.Case 2. d is odd.(8)n=∑i=0dki=∑i=0d−1/2k2i+k2i+1≥∑i=0d−1/23=3d+12,and makingd subject of the formula, we obtain d≤2n/3−1, thereby completing our proof. To show that this bound is asymptotically sharp, consider the following graph: for positive integers π0,π1,…,πd, Pdπ0,π1,…,πd is the graph obtained from a path, Pd+1, with d+1 vertices, by replacing every vertex vi by the null graph Nπi, where(9)πi=1,ifi=0ord,2,ifi=1ord−1,1,ifi≡0mod2,2,ifi≡1mod2,and making every vertex inNπq adjacent to every vertex in Nπs whenever Nπq and Nπs have replaced adjacent vertices of Pd+1. Note that Pdπ0,π1,…,πd is a 2-edge-connected triangle-free graph and that whenever d is even, diamPdπ0,π1,…,πd=2n−2/3.
The following corollary to Theorem1 follows from the fact that every bipartite graph is also triangle free and the observation that the corresponding extremal graph for the same theorem is bipartite.Corollary 1.
LetG be a bipartite graph of order n and diameter d≥1. If λ=2, then(10)diamG≤2n3−1.
Further, this inequality is best possible.
Although it is not necessarily the scope of this paper, we point out that the above bound also holds and is tight for graphs which are not triangle free, with the same extremal graph being applicable. Mukwembi [5] investigated graphs with edge connectivity λ∈3,4 and came up with the following.Theorem 2.
LetG be a λ-edge-connected graph, λ∈3,4, of order n; then, diamG≤⌊n−1/2⌋. Further, this inequality is best possible with the exception of a small constant.
While this bound is for graphs which are unrestricted with respect to subgraphs, it is also tight for both bipartite and triangle-free graphs. To see this, consider the graphPdπ0,π1,…,πd with all the same properties as before, except that(11)πi=1,ifi=0ord,λ,ifi=1ord−1,λ−1,ifi=2ord−2,2,otherwise.
LetdiamPdπ0,π1,…,πd=d. Observe that Pdπ0,π1,…,πd is bipartite and triangle free and that if λ=3, then d=n−2/2, and if λ=4, then d=n−6/2. The case where λ=5 is rather atypical and requires added attention; hence, we earmark it for one of the main results in our paper. For λ≥6, we have the following.Theorem 3.
LetG be a triangle-free, λ-edge-connected graph, λ≥6, of order n. Then,(12)diamG≤2nλ+1.
Further, this inequality is best possible with the exception of a small constant.Proof.
An application of the Whitney inequality,δ≥λ, to equation (3) yields the desired result. Now, let p∈ℕ, be a number such that it is the least number satisfying the inequality λ≤p2. To show that this bound is tight, consider the graph Pdπ0,π1,…,πd with all the same properties as before, except that(13)πi=1,ifi=0ord,λ,ifi=1ord−1,λ−1,ifi=2ord−2,p,ifi≡0or1mod4,λ−p,ifi≡2or3mod4.
ObservePdπ0,π1,…,πd is a λ-edge-connected triangle-free graph and that whenever d≡1mod4, then diamPdπ0,π1,…,πd=2n/λ−3.
The following corollary to Theorem3 follows from the fact that every bipartite graph is also triangle free and the observation that the corresponding extremal graph for the same theorem is bipartite.Corollary 2.
LetG be a λ-edge-connected, bipartite graph, λ≥6, of order n. Then,(14)diamG≤2nλ+1.
Further, this inequality is best possible with the exception of a small constant.
This paper also aims to bound the diameter of any bipartite or triangle-free graph with respect to size and edge connectivity. It is clear that the bounddiamG≤m/λ holds for whatever value of λ we choose. This bound, however, is only tight when λ∈1,2,4, with the extremal graphs for these values of λ being the same as those offered up for similar values of λ when we were discussing bounds on diameter with respect to order and edge connectivity. For λ≥6, the following theorem, which at first glance seems counter intuitive, holds true.Theorem 4.
LetG be a λ-edge-connected, λ≥6, triangle-free graph of size m; then, diamG≤4m/λ2+1. Further, this inequality is best possible with the exception of a small constant.Proof.
An application of the Whitney inequality,δ≥λ, and the handshaking lemma, ∑x∈Vdegx=2m, yields the inequality nλ≤2m, and applying this to Theorem 3, we obtain the desired result. The extremal graph for this bound is the same as the one for Theorem 3 and has diameter diamG=4m/λ2−2 whenever diamG≡2mod4.
The following corollary to Theorem4 follows from the fact that every bipartite graph is also triangle free and the observation that the corresponding extremal graph for the same theorem is bipartite.Corollary 3.
LetG be a λ-edge-connected bipartite graph of size m; then, diamG≤4m/λ2+1. Further, this inequality is best possible with the exception of a small constant.
The cases whereλ=3 and λ=5 need more care and as such have been allotted space among our main results.


## 1.1. Observation

LetG be a λ-edge-connected graph, V1,V2⊂V with V1∩V2=∅. Clearly, EV1,V2≤V1V2. If EV1,V2 is a disconnecting set of G, then EV1,V2≥λG so that V1V2≥λG. Let v∈V. Note also that for i=0,1,…,ecGv−1, it is clear that ENi,Ni+1 is a disconnecting set of G.The following fact follows from the above observation.Fact 1.
kiki+1≥λ for all i=1,2,…,ecGv−1.
The following useful facts follow from the well-known AM-GM inequalityab≤a+b/22. That is to say, the geometric mean of two (positive) real numbers never exceeds their arithmetic mean.Fact 2.
For positive integersa and b, if ab≥2, then a+b≥3.Fact 3.
For positive integersa and b, if ab≥5, then a+b≥5.
It is the purpose of this paper to bound the diameter of any triangle-free graph with respect to order and edge connectivity. We have dealt with the case whereinλ=1 and we now proceed to higher values of the same.Theorem 1.
LetG be a triangle-free graph of order n and diameter d≥1. If λ=2, then(6)diamG≤2n3−1.
Further, this inequality is best possible.Proof.
Note that sinceG is 2-edge-connected by the condition of the lemma, we have kiki+1≥2 from Fact 1. From this and Fact 2, we have ki+ki+1≥3. Thus, we have two cases.Case 1. d is even.(7)n=∑i=0dki=∑i=0d−2/2k2i+k2i+1+kd≥∑i=0d−2/23+1=3d2+1,and makingd subject of the formula, we obtain d≤2n/3−2/3.Case 2. d is odd.(8)n=∑i=0dki=∑i=0d−1/2k2i+k2i+1≥∑i=0d−1/23=3d+12,and makingd subject of the formula, we obtain d≤2n/3−1, thereby completing our proof. To show that this bound is asymptotically sharp, consider the following graph: for positive integers π0,π1,…,πd, Pdπ0,π1,…,πd is the graph obtained from a path, Pd+1, with d+1 vertices, by replacing every vertex vi by the null graph Nπi, where(9)πi=1,ifi=0ord,2,ifi=1ord−1,1,ifi≡0mod2,2,ifi≡1mod2,and making every vertex inNπq adjacent to every vertex in Nπs whenever Nπq and Nπs have replaced adjacent vertices of Pd+1. Note that Pdπ0,π1,…,πd is a 2-edge-connected triangle-free graph and that whenever d is even, diamPdπ0,π1,…,πd=2n−2/3.
The following corollary to Theorem1 follows from the fact that every bipartite graph is also triangle free and the observation that the corresponding extremal graph for the same theorem is bipartite.Corollary 1.
LetG be a bipartite graph of order n and diameter d≥1. If λ=2, then(10)diamG≤2n3−1.
Further, this inequality is best possible.
Although it is not necessarily the scope of this paper, we point out that the above bound also holds and is tight for graphs which are not triangle free, with the same extremal graph being applicable. Mukwembi [5] investigated graphs with edge connectivity λ∈3,4 and came up with the following.Theorem 2.
LetG be a λ-edge-connected graph, λ∈3,4, of order n; then, diamG≤⌊n−1/2⌋. Further, this inequality is best possible with the exception of a small constant.
While this bound is for graphs which are unrestricted with respect to subgraphs, it is also tight for both bipartite and triangle-free graphs. To see this, consider the graphPdπ0,π1,…,πd with all the same properties as before, except that(11)πi=1,ifi=0ord,λ,ifi=1ord−1,λ−1,ifi=2ord−2,2,otherwise.
LetdiamPdπ0,π1,…,πd=d. Observe that Pdπ0,π1,…,πd is bipartite and triangle free and that if λ=3, then d=n−2/2, and if λ=4, then d=n−6/2. The case where λ=5 is rather atypical and requires added attention; hence, we earmark it for one of the main results in our paper. For λ≥6, we have the following.Theorem 3.
LetG be a triangle-free, λ-edge-connected graph, λ≥6, of order n. Then,(12)diamG≤2nλ+1.
Further, this inequality is best possible with the exception of a small constant.Proof.
An application of the Whitney inequality,δ≥λ, to equation (3) yields the desired result. Now, let p∈ℕ, be a number such that it is the least number satisfying the inequality λ≤p2. To show that this bound is tight, consider the graph Pdπ0,π1,…,πd with all the same properties as before, except that(13)πi=1,ifi=0ord,λ,ifi=1ord−1,λ−1,ifi=2ord−2,p,ifi≡0or1mod4,λ−p,ifi≡2or3mod4.
ObservePdπ0,π1,…,πd is a λ-edge-connected triangle-free graph and that whenever d≡1mod4, then diamPdπ0,π1,…,πd=2n/λ−3.
The following corollary to Theorem3 follows from the fact that every bipartite graph is also triangle free and the observation that the corresponding extremal graph for the same theorem is bipartite.Corollary 2.
LetG be a λ-edge-connected, bipartite graph, λ≥6, of order n. Then,(14)diamG≤2nλ+1.
Further, this inequality is best possible with the exception of a small constant.
This paper also aims to bound the diameter of any bipartite or triangle-free graph with respect to size and edge connectivity. It is clear that the bounddiamG≤m/λ holds for whatever value of λ we choose. This bound, however, is only tight when λ∈1,2,4, with the extremal graphs for these values of λ being the same as those offered up for similar values of λ when we were discussing bounds on diameter with respect to order and edge connectivity. For λ≥6, the following theorem, which at first glance seems counter intuitive, holds true.Theorem 4.
LetG be a λ-edge-connected, λ≥6, triangle-free graph of size m; then, diamG≤4m/λ2+1. Further, this inequality is best possible with the exception of a small constant.Proof.
An application of the Whitney inequality,δ≥λ, and the handshaking lemma, ∑x∈Vdegx=2m, yields the inequality nλ≤2m, and applying this to Theorem 3, we obtain the desired result. The extremal graph for this bound is the same as the one for Theorem 3 and has diameter diamG=4m/λ2−2 whenever diamG≡2mod4.
The following corollary to Theorem4 follows from the fact that every bipartite graph is also triangle free and the observation that the corresponding extremal graph for the same theorem is bipartite.Corollary 3.
LetG be a λ-edge-connected bipartite graph of size m; then, diamG≤4m/λ2+1. Further, this inequality is best possible with the exception of a small constant.
The cases whereλ=3 and λ=5 need more care and as such have been allotted space among our main results.


## 2. Results

### 2.1. 3-Edge-Connected Graphs

LetG be a 3-edge-connected triangle-free graph of size m and diameter d>1.For an example of a 3-edge-connected graph, consider the following graph: for positive integersπ0,π1,…,πd, Pdπ0,π1,…,πd is the graph obtained from a path, Pd+1, with d+1 vertices, by replacing every vertex vi by the null graph Nπi, where(15)πi=1,ifi=0ord,3,otherwise,and making every vertex in Nπq adjacent to every vertex in Nπs whenever Nπq and Nπs have replaced adjacent vertices of Pd+1.Letx,y∈V be fixed vertices in G such that dx,y=diamG=d. For any 0≤i≤d, let Ni=v∈VdGx,v=i and ki=Ni. For any 0≤j,l≤d, where j<l, let Mj,l=e∈Ee∈E∪i=jlNi,∪i=jlNi and mj,l=Mj,l. Also, let Mi be the set of edges between vertices in the same distance layer, that is to say, Mi=ENi,Ni, and let the cardinality of the same set be given by mi=Mi. Further, Mj,l=Mj,l−Mj∪Ml and mj,l=Mj,l.Lemma 1.
For eachi∈1,2,…,d−1, if ki≥2, then mi−1,i+1≥7.Proof.
SinceG is a 3-edge-connected graph, we have that mi−1,i,mi,i+1≥3 so that if Mi is nonempty, we are immediately satisfied since mi−1,i+1=mi−1,i+mi,i+1+mi≥3+3+1=7. Hence, suppose that Mi is empty. Suppose also, to the contrary, that mi−1,i+1<7. Since G is 3-edge-connected, we see that mi−1,i+1≥mi−1,i+mi,i+1≥3+3=6. Thus, by our supposition, mi−1,i+1=6 and mi−1,i=mi,i+1=3. Now, choose any two vertices in Ni, say a and b. Note that dega,degb≥3 since G is 3-edge-connected. Further a and b share no edges since Mi is empty; thus, of the six edges in Mi−1,i+1, we have that three are incident with a and the other three are incident with b. Also, since there necessarily exists a path from Ni−1 to Ni+1 and mi−1,i=mi,i+1=3, we are guaranteed that a and b are each incident with at least an edge in each of the sets Mi−1,i and Mi,i+1. And since for each of a and b there are three edges and two sets, it is necessary that one of the edges incident with a (or b) be in a set different from the other two edges incident with a (or b). For a, label this edge ea, and for b, label this edge eb. Observe that G−ea,eb is disconnected contradicting our supposition that G is 3-edge-connected. This immediately settles our lemma.Lemma 2.
For eachi∈1,2,…,d−3, if mi−1,i+1=6, then mi+1,i+3≥9.Proof.
By the condition of the current lemma and by Lemma1, we have ki=1. From this and again using the condition of the current lemma combined with the fact that G is 3-edge-connected, we see that ki−1=ki+1=3 and that mi−1,i=mi,i+1=3. Note also that Mi+1 is empty since G is triangle free and all the vertices in Ni+1 are adjacent to the single vertex in Ni. Hence, the vertices in Ni+1 share no edges and consequently mi,i+1+mi+1,i+2≥δki+1=9 which yields mi+1,i+2≥9−mi,i+1=6. Note that mi+2,i+3≥3 since G is 3-edge-connected, and hence mi+1,i+3≥mi+1,i+2+mi+2,i+3≥6+3=9, thereby proving our lemma.Lemma 3.
For eachi∈3,4,…,d−1, if mi−1,i+1=6, then mi−3,i−1≥9.Proof.
We can get the desired conclusion by arguing as in the proof of Lemma2.Lemma 4.
For eachi∈2,4,…,d−2, mi−2,i+2≥14.Proof.
Note that sinceλ=3, we have that mi−2,i≥mi−2,i−1+mi−1,i≥3+3=6. Also, mi,i+2≥mi,i+1+mi+1,i+2≥3+3=6. Hence, we obtain the following:Ifmi−2,i,mi,i+2≥7, we have mi−2,i+2≥mi−2,i+mi,i+2≥7+7=14 and we are done.Ifmi−2,i=6, then we have, by Lemma 2, mi−2,i+2≥mi−2,i+mi,i+2≥6+9=15 and we are done.Ifmi,i+2=6, then we have, by Lemma 3, mi−2,i+2≥mi−2,i+mi,i+2≥9+6=15, thereby settling our lemma.
Throughout the rest of this result we definec∈0,1,2,3 as a number such that d≡cmod4 where d=diamG.
The following theorem provides a tight upper bound on the diameter of a 3-edge-connected triangle-free graph of prescribed size.Theorem 5.
LetG be a 3-edge-connected triangle-free graph of size m. Then,(16)diamG≤2m+37.
This inequality is, apart from an additive constant, best possible.Proof.
Note thatm=m0,d≥∑i=0d−c−4/4m4i,4i+4+md−c,d−c+1+md−c+1,d−c+2+md−c+2,d−c+3 where mi,i+1=0 whenever i≥d. Hence, there are four cases to consider.Case 1. d≡0mod4. If this is so, then c=0, and we have, by Lemma 4,(17)m=m0,d≥∑i=0d−4/4m4i,4i+4≥∑i=0d−4/414=14d4,and makingd subject of the formula, we obtain d≤2m/7.Case 2. d≡1mod4. If this is so, then c=1, and we have the following by Lemma 4 and the fact that mi,i+1≥λ=3 for all i<d:(18)m=m0,d≥∑i=0d−5/4m4i,4i+4+md−1,d≥∑i=0d−5/414+3=14d−14+3,and makingd subject of the formula, we obtain d≤2m+1/7.Case 3. d≡2mod4. If this is so, then c=2, and we have the following by Lemma 4 and the fact that mi,i+1≥λ=3 for all i<d:(19)m=m0,d≥∑i=0d−6/4m4i,4i+4+md−2,d−1+md−1,d≥∑i=0d−6/414+3+3=14d−24+6,and makingd subject of the formula, we obtain d≤2m+2/7.Case 4. d≡3mod4. If this is so, then c=3, and we have the following by Lemma 4 and the fact that mi,i+1≥λ=3 for all i<d:(20)m=m0,d≥∑i=0d−7/4m4i,4i+4+md−3,d−2+md−2,d−1+md−1,d≥∑i=0d−7/414+3+3+3=14d−34+9,and makingd subject of the formula, we obtain d≤2m+3/7.
Hence, considering all four cases, we obtaind≤2m+3/7 as desired. To show that this bound is tight, consider the graph Pdπ0,π1,…,πd with all the same properties as before, except that(21)πi=1,ifi=0ord,3,ifi=1ord−1,2,otherwise,mi,i+1=3,ifi=0ord−1,6,ifi=1ord−2,3,ifiis even,4,ifiis odd.
Observe that wheneverd is even, diamPdπ0,π1,…,πd=2m−8/7.
The following corollary to Theorem5 follows from the fact that every bipartite graph is also triangle free and the observation that the corresponding extremal graph for the same theorem is bipartite.Corollary 4.
LetG be a 3-edge-connected bipartite graph of size m. Then,(22)diamG≤2m+37.
This inequality is, apart from an additive constant, best possible.
The following definitions and lemmas will be used in the study of 5-edge-connected graphs.


### 2.2. 5-Edge-Connected Graphs

LetG be a 5-edge-connected triangle-free graph of order n and diameter d>1.For an example of a 5-edge-connected graph, consider the following graph: for positive integersπ0,π1,…,πd, Pdπ0,π1,…,πd is the graph obtained from a path, Pd+1, with d+1 vertices, by replacing every vertex vi by the null graph Nπi, where(23)πi=1,ifi=0ord,5,otherwise,and making every vertex in Nπq adjacent to every vertex in Nπs whenever Nπq and Nπs have replaced adjacent vertices of Pd+1.Letx,y∈V be fixed vertices in G such that dx,y=diamG=d and let Ni=v∈VdGx,v=i for any 0≤i≤d and ki=Ni.Lemma 5.
For eachi∈0,1,…,d−1, ki+ki+1≥5.Proof.
Note that sinceG is 5-edge-connected, we have kiki+1≥5 by Fact 1. Because of this and as a consequence of Fact 3, we obtain ki+ki+1≥5.
The following two lemmas follow immediately from Lemma5.Lemma 6.
Fori∈1,2,…,d−1, if ki=1, then ki−1+ki+ki+1≥9.Lemma 7.
Fori∈1,2,…,d−1, if ki=2, then ki−1+ki+ki+1≥8.Lemma 8.
Fori∈1,2,…,d−1, if ki≥3, then ki−1+ki+ki+1≥8.Proof.
There are two cases to consider.Case 1. There exists an edge, ab∈E, such that a,b∈Ni.SinceG is triangle free, the effect of this is that a and b share no neighbors, that is to say, Na∩Nb=∅. Note that Na∪Nb⊆Ni−1∪Ni∪Ni+1 and Na,Nb≥δ≥λ=5. Hence, ki−1+ki+ki+1≥Na∪Nb=Na+Nb≥5+5=10.Case 2. There are no adjacent vertices in Ni.Leta∈Ni. Since there are no adjacent vertices in Ni, we see that Na∩Ni=∅. Also, Na⊆Ni−1∪Ni+1 and Na≥δ≥λ=5. Hence, ki−1+ki+ki+1≥Ni∪Na=Ni+Na≥3+5=8.Lemma 9.
For eachi∈1,2,…,d−1, ki−1+ki+ki+1≥8.Proof.
There are three cases to consider.Case 1. ki=1.If this is so, then we are done by Lemma6.Case 2. ki=2.If this is so, then we are done by Lemma7.Case 3. ki≥3.If this is so, then we are done by Lemma8.
Throughout the rest of this paper we definec∈0,1,2 as a number such that d−c≡2mod3 where d=diamG.
The following theorem provides a tight upper bound on the diameter of a 5-edge-connected triangle-free graph of prescribed order.Theorem 6.
LetG be a 5-edge-connected triangle-free graph of order n. Then,(24)diamG≤3n−38.
This inequality is, apart from an additive constant, best possible.Proof.
Note thatn=∑i=0dki=∑i=0d−c−2/3k3i+k3i+1+k3i+2+kd−c+1+kd−c+2 where ki=0 whenever i>d. Hence, there are three cases to consider.Case 1. d≡0mod3. If this is so, then c=1, and we have the following by Lemma 9 and the fact that kd≥1 since Nd is nonempty:(25)n=∑i=0dki=∑i=0d−1−2/3k3i+k3i+1+k3i+2+kd≥∑i=0d−3/3k3i+k3i+1+k3i+2+kd≥∑i=0d−3/38+1=d−33+18+1=8d3+1,and makingd subject of the formula, we obtain d≤3n−3/8.Case 2. d≡1mod3. If this is so, then c=2, and we have the following by Lemma 9 and Lemma 5:(26)n=∑i=0dki=∑i=0d−2−2/3k3i+k3i+1+k3i+2+kd−1+kd≥∑i=0d−4/3k3i+k3i+1+k3i+2+kd−1+kd≥∑i=0d−4/38+5=d−43+18+5=8d−83+5,and makingd subject of the formula, we obtain d≤3n−7/8.Case 3. d≡2mod3. If this is so, then c=0, and we have the following by Lemma 9:(27)n=∑i=0dki=∑i=0d−0−2/3k3i+k3i+1+k3i+2≥∑i=0d−2/3k3i+k3i+1+k3i+2≥∑i=0d−2/38=d−23+18=8d+83,and makingd subject of the formula, we obtain d≤3n/8−1.
Hence, considering all three cases, we obtaind≤3n−3/8 as desired. To show that this bound is tight, consider the graph Pdπ0,π1,…,πd with all the same properties as before, except that(28)πi=1,ifi=0ord,5,ifi=1ord−1,4,ifi=2ord−2,2,ifi≡0mod3,3,ifi≡1or2mod3.
Observe that wheneverd≡2mod3, diamPdπ0,π1,…,πd=3n−20/8.
The following corollary to Theorem6 follows from the fact that every bipartite graph is also triangle free and the observation that the corresponding extremal graph for the same theorem is bipartite.Corollary 5.
LetG be a 5-edge-connected bipartite graph of order n. Then,(29)diamG≤3n−38.
This inequality is, apart from an additive constant, best possible.
Our final result is a tight upper bound on the diameter of a 5-edge-connected bipartite graph with respect to its size. To obtain the said bound, we need the following definitions and lemmas. LetG be a 5-edge-connected bipartite graph of size m and diameter d>1. Let x,y∈V be fixed vertices in G such that dx,y=diamG=d and let Ni=v∈VdGx,v=i for any 0≤i≤d and ki=Ni. For j<l, let Mj,l=e∈Ee∈E∪i=jlNi,∪i=jlNi for any 0≤j≤d−1 and mj,l=Mj,l. Also, let Mj,l=Mj,l−ENj,Nj∪ENl,Nl and mj,l=Mj,l. Mi is simply the set of edges between vertices in the same distance layer, that is to say, Mi=ENi,Ni, and the cardinality of the same set is given by mi=Mi.Lemma 10.
For eachi∈0,1,…,d, Mi is empty.Proof.
The desired conclusion follows from the assumption thatG is bipartite.Lemma 11.
For eachi∈1,…,d−1, if ki+1+ki+2≥6, then mi,i+3≥21.Proof.
Note that, by Lemma10, Mi=∅. Since ki+1+ki+2≥6, choose any six vertices from Ni+1∪Ni+2. Label the set of vertices we have chosen from Ni+1 as Ni+1′ and the set of vertices we have chosen from Ni+2 as Ni+2′. Identify the edges incident to vertices in Ni+1′ and Ni+2′ as EINi+1′ and EINi+2′, respectively. Note that mi,i+3≥EINi+1′∪EINi+2′=EINi+1′+EINi+2′−EINi+1′∩EINi+2′. Observe that since Ni+1′+Ni+2′=6 and since δ≥λ≥5, we have, by Lemma 10, that EINi+1′+EINi+2′≥∑x∈Ni+1′∪Ni+2′degx≥6δ=30. Since Ni+1′∩Ni+2′=∅ and using the AM-GM inequality, we observe that EINi+1′∩EINi+2′=ENi+1′,Ni+2′≤Ni+1′Ni+2′≤Ni+1′+Ni+2′/22=9. Hence, mi,i+3≥EINi+1′∪EINi+2′=EINi+1′+EINi+2′−EINi+1′∩EINi+2′≥30−9=21, and we are done.
The following fact stems from Lemma5 and the observation that every bipartite graph is also triangle free.Fact 4.
For eachi∈0,1,…,d−1, ki+ki+1≥5.
Fori∈1,2,…,d−3, let S be an induced subgraph of G such that VS=∪j=ii+3Nj. We then have the following useful definition.Definition 1.
S is a scant subgraph of G (or simply, S is scant) if mi,i+3<21.Lemma 12.
IfS, where VS=∪j=ii+3Nj, is scant, then ki+1,ki+2=2,3 or ki+1,ki+2=3,2.Proof.
ByFact 4, Lemma 11, and by the condition of the current lemma, we have that ki+1+ki+2=5. Hence, ki+1,ki+2∈1,4,2,3,3,2,4,1, and it is sufficient to prove the current lemma if we can show that ki+1,ki+2≠1. Suppose to the contrary that ki+1=1. If this is so, then ki+2=4, and since Ni+1∩Ni+2=∅, we obtain ENi+1,Ni+2≤ki+1ki+2=4<5=λ, contradicting the condition that G is 5-edge-connected. The same argument is to be used for the case where ki+2=1, hence settling our lemma.
As a consequence of Lemma12, we further add the following definitions.Definition 2.
LetS, where VS=∪j=ii+3Nj, be a scant subgraph of G. If ki+1,ki+2=2,3, we say S is scant-left, and if ki+1,ki+2=3,2, we say S is scant-right.Lemma 13.
IfS, where VS=∪j=ii+3Nj, is scant, then mi,i+3=20.Proof.
By the condition of the current lemma and by Lemma12, we have that ki+1,ki+2=2,3 or ki+1,ki+2=3,2. Hence, there are two cases to consider.Case 1. ki+1,ki+2=2,3.Note thatmi,i+3≥mi,i+1+mi+1,i+3. Note also that since, by Lemma 10, Mi+2 is empty and since δ≥λ≥5, we have that mi+1,i+3=∑x∈Ni+2degx≥δki+2=15. Further, observe that Mi,i+1 is a disconnecting set of G, and hence mi,i+1≥λ=5. Thus, we have mi,i+3≥mi,i+1+mi+1,i+3≥5+15=20.Case 2. ki+1,ki+2=3,2.We can get the desired conclusion by arguing as in case 1.Lemma 14.
(a)
IfS, where VS=∪j=ii+3Nj, is scant-left, then mi−3,i≥25.(b)
IfS, where VS=∪j=ii+3Nj, is scant-right, then mi+3,i+6≥25.Proof.
We will show that the result holds for (a) as it follows analogously for (b).
(a)ki+2=3 by the condition of the lemma, and hence we have that mi+1,i+3≥∑x∈Ni+2degx≥δki+2=15. Also, mi,i+3≤20, by the condition of the lemma. Hence, mi,i+1≤mi,i+3−mi+1,i+3≤20−15=5. Note that by the condition of the lemma and by Fact 4, we have ki≥3. If each vertex in Ni is adjacent to both vertices in Ni+1, then mi,i+1≥kiki+1≥2ki≥6 which contradicts our deduction that mi,i+1<6. Hence, there is at least one vertex, say a, in Ni which is adjacent to at most one vertex in Ni+1. By Lemma 10 and since dega≥δ≥λ≥5, we see that a has at least four neighbors in Ni−1, that is to say, ki−1≥4. Note that mi−3,i≥mi−3,i−2+mi−2,i. Note also that since, by Lemma 10, Mi−1 is empty and since δ≥λ≥5, we have that mi−2,i=∑x∈Ni−1degx≥δki−1≥20. Further, observe that Mi−3,i−2 is a disconnecting set of G, and hence mi−3,i−2≥λ=5. Thus, we have mi−3,i≥mi−3,i−2+mi−2,i≥5+20=25.
Throughout the remainder of this paper, we assume thatdiamG=d≡cmod3, c∈0,1,2, and we define the set I=0,1,…,d−c−3/3. For p∈I, we define Sp=∪j=3p3p+3Ni. As a result of the previous lemma, we have the following definition.Definition 3.
Forp∈I, we say Sp is a surplus subgraph of G (or simply, Sp is a surplus) if m3p,3p+3≥25.Lemma 15.
m0,d−c≥21I.Proof.
We have three cases to consider.Case 1. For all p∈I, Sp is not scant.If this is so, thenm0,d−c≥∑p∈Im3p,3p+3≥21I and we are done.In the remaining two cases, we assume that for at least onep∈I, Sp is scant. Let A=pjj∈1,2,…,α and B=qjj∈1,2,…,β such that Sp is a left-scant whenever p∈A and Sp is a right-scant whenever p∈B.Case 2. α≥β.If this is so, we have the following. LetC1=p−1p∈A; then, by Lemma 14, Sp is a surplus whenever p∈C1⊂I. Also, let D1=I−A∪B∪C1. Notice that C1=A and since A, B, and C1 are mutually exclusive sets, we have D1=I−A−B−C1=I−2A−B. Further, since α≥β, we have that 3A−B>0. Hence, we obtain m0,d−c≥∑p∈Im3p,3p+3=∑p∈D1m3p,3p+3+∑p∈Am3p,3p+3+∑p∈Bm3p,3p+3+∑p∈C1m3p,3p+3 ≥20A+20B+25C1+21D1=20A+20B+25A+21I−2A−B=21I+3A−B≥21I and we are done.Case 3. α<β.We can get the desired conclusion by arguing as in case 2.
Our final theorem below provides a tight upper bound on the diameter of a 5-edge-connected bipartite graph of prescribed size.Theorem 7.
LetG be a 5-edge-connected bipartite graph of size m. Then,(30)d=diamG≤m+47.
This inequality is, apart from an additive constant, best possible.Proof.
There are three cases to consider.Case 1. d≡0mod3.If this is so, thenc=0 and(31)m=m0,d≥∑p∈Im3p,3p+3≥21I=21d−33+1=7d.Makingd subject of the formula, we get d≤m/7.Case 2. d≡1mod3.If this is so, thenc=1 and(32)m=m0,d≥∑p∈Im3p,3p+3+md−1,d≥21I+5=21d−1−33+1+5=7d−2.Makingd subject of the formula, we get d≤m+2/7.Case 3. d≡2mod3.If this is so, thenc=2 and(33)m=m0,d≥∑p∈Im3p,3p+3+md−2,d−1+md−1,d≥21I+5+5=21d−2−33+1+10=7d−4.Makingd subject of the formula, we get d≤m+4/7. To show that this bound is tight, consider the extremal graph given in Theorem 6. Observe that whenever d≡0mod3, diamPdπ0,π1,…,πd=m/7.


## 2.1. 3-Edge-Connected Graphs

LetG be a 3-edge-connected triangle-free graph of size m and diameter d>1.For an example of a 3-edge-connected graph, consider the following graph: for positive integersπ0,π1,…,πd, Pdπ0,π1,…,πd is the graph obtained from a path, Pd+1, with d+1 vertices, by replacing every vertex vi by the null graph Nπi, where(15)πi=1,ifi=0ord,3,otherwise,and making every vertex in Nπq adjacent to every vertex in Nπs whenever Nπq and Nπs have replaced adjacent vertices of Pd+1.Letx,y∈V be fixed vertices in G such that dx,y=diamG=d. For any 0≤i≤d, let Ni=v∈VdGx,v=i and ki=Ni. For any 0≤j,l≤d, where j<l, let Mj,l=e∈Ee∈E∪i=jlNi,∪i=jlNi and mj,l=Mj,l. Also, let Mi be the set of edges between vertices in the same distance layer, that is to say, Mi=ENi,Ni, and let the cardinality of the same set be given by mi=Mi. Further, Mj,l=Mj,l−Mj∪Ml and mj,l=Mj,l.Lemma 1.
For eachi∈1,2,…,d−1, if ki≥2, then mi−1,i+1≥7.Proof.
SinceG is a 3-edge-connected graph, we have that mi−1,i,mi,i+1≥3 so that if Mi is nonempty, we are immediately satisfied since mi−1,i+1=mi−1,i+mi,i+1+mi≥3+3+1=7. Hence, suppose that Mi is empty. Suppose also, to the contrary, that mi−1,i+1<7. Since G is 3-edge-connected, we see that mi−1,i+1≥mi−1,i+mi,i+1≥3+3=6. Thus, by our supposition, mi−1,i+1=6 and mi−1,i=mi,i+1=3. Now, choose any two vertices in Ni, say a and b. Note that dega,degb≥3 since G is 3-edge-connected. Further a and b share no edges since Mi is empty; thus, of the six edges in Mi−1,i+1, we have that three are incident with a and the other three are incident with b. Also, since there necessarily exists a path from Ni−1 to Ni+1 and mi−1,i=mi,i+1=3, we are guaranteed that a and b are each incident with at least an edge in each of the sets Mi−1,i and Mi,i+1. And since for each of a and b there are three edges and two sets, it is necessary that one of the edges incident with a (or b) be in a set different from the other two edges incident with a (or b). For a, label this edge ea, and for b, label this edge eb. Observe that G−ea,eb is disconnected contradicting our supposition that G is 3-edge-connected. This immediately settles our lemma.Lemma 2.
For eachi∈1,2,…,d−3, if mi−1,i+1=6, then mi+1,i+3≥9.Proof.
By the condition of the current lemma and by Lemma1, we have ki=1. From this and again using the condition of the current lemma combined with the fact that G is 3-edge-connected, we see that ki−1=ki+1=3 and that mi−1,i=mi,i+1=3. Note also that Mi+1 is empty since G is triangle free and all the vertices in Ni+1 are adjacent to the single vertex in Ni. Hence, the vertices in Ni+1 share no edges and consequently mi,i+1+mi+1,i+2≥δki+1=9 which yields mi+1,i+2≥9−mi,i+1=6. Note that mi+2,i+3≥3 since G is 3-edge-connected, and hence mi+1,i+3≥mi+1,i+2+mi+2,i+3≥6+3=9, thereby proving our lemma.Lemma 3.
For eachi∈3,4,…,d−1, if mi−1,i+1=6, then mi−3,i−1≥9.Proof.
We can get the desired conclusion by arguing as in the proof of Lemma2.Lemma 4.
For eachi∈2,4,…,d−2, mi−2,i+2≥14.Proof.
Note that sinceλ=3, we have that mi−2,i≥mi−2,i−1+mi−1,i≥3+3=6. Also, mi,i+2≥mi,i+1+mi+1,i+2≥3+3=6. Hence, we obtain the following:Ifmi−2,i,mi,i+2≥7, we have mi−2,i+2≥mi−2,i+mi,i+2≥7+7=14 and we are done.Ifmi−2,i=6, then we have, by Lemma 2, mi−2,i+2≥mi−2,i+mi,i+2≥6+9=15 and we are done.Ifmi,i+2=6, then we have, by Lemma 3, mi−2,i+2≥mi−2,i+mi,i+2≥9+6=15, thereby settling our lemma.
Throughout the rest of this result we definec∈0,1,2,3 as a number such that d≡cmod4 where d=diamG.
The following theorem provides a tight upper bound on the diameter of a 3-edge-connected triangle-free graph of prescribed size.Theorem 5.
LetG be a 3-edge-connected triangle-free graph of size m. Then,(16)diamG≤2m+37.
This inequality is, apart from an additive constant, best possible.Proof.
Note thatm=m0,d≥∑i=0d−c−4/4m4i,4i+4+md−c,d−c+1+md−c+1,d−c+2+md−c+2,d−c+3 where mi,i+1=0 whenever i≥d. Hence, there are four cases to consider.Case 1. d≡0mod4. If this is so, then c=0, and we have, by Lemma 4,(17)m=m0,d≥∑i=0d−4/4m4i,4i+4≥∑i=0d−4/414=14d4,and makingd subject of the formula, we obtain d≤2m/7.Case 2. d≡1mod4. If this is so, then c=1, and we have the following by Lemma 4 and the fact that mi,i+1≥λ=3 for all i<d:(18)m=m0,d≥∑i=0d−5/4m4i,4i+4+md−1,d≥∑i=0d−5/414+3=14d−14+3,and makingd subject of the formula, we obtain d≤2m+1/7.Case 3. d≡2mod4. If this is so, then c=2, and we have the following by Lemma 4 and the fact that mi,i+1≥λ=3 for all i<d:(19)m=m0,d≥∑i=0d−6/4m4i,4i+4+md−2,d−1+md−1,d≥∑i=0d−6/414+3+3=14d−24+6,and makingd subject of the formula, we obtain d≤2m+2/7.Case 4. d≡3mod4. If this is so, then c=3, and we have the following by Lemma 4 and the fact that mi,i+1≥λ=3 for all i<d:(20)m=m0,d≥∑i=0d−7/4m4i,4i+4+md−3,d−2+md−2,d−1+md−1,d≥∑i=0d−7/414+3+3+3=14d−34+9,and makingd subject of the formula, we obtain d≤2m+3/7.
Hence, considering all four cases, we obtaind≤2m+3/7 as desired. To show that this bound is tight, consider the graph Pdπ0,π1,…,πd with all the same properties as before, except that(21)πi=1,ifi=0ord,3,ifi=1ord−1,2,otherwise,mi,i+1=3,ifi=0ord−1,6,ifi=1ord−2,3,ifiis even,4,ifiis odd.
Observe that wheneverd is even, diamPdπ0,π1,…,πd=2m−8/7.
The following corollary to Theorem5 follows from the fact that every bipartite graph is also triangle free and the observation that the corresponding extremal graph for the same theorem is bipartite.Corollary 4.
LetG be a 3-edge-connected bipartite graph of size m. Then,(22)diamG≤2m+37.
This inequality is, apart from an additive constant, best possible.
The following definitions and lemmas will be used in the study of 5-edge-connected graphs.


## 2.2. 5-Edge-Connected Graphs

LetG be a 5-edge-connected triangle-free graph of order n and diameter d>1.For an example of a 5-edge-connected graph, consider the following graph: for positive integersπ0,π1,…,πd, Pdπ0,π1,…,πd is the graph obtained from a path, Pd+1, with d+1 vertices, by replacing every vertex vi by the null graph Nπi, where(23)πi=1,ifi=0ord,5,otherwise,and making every vertex in Nπq adjacent to every vertex in Nπs whenever Nπq and Nπs have replaced adjacent vertices of Pd+1.Letx,y∈V be fixed vertices in G such that dx,y=diamG=d and let Ni=v∈VdGx,v=i for any 0≤i≤d and ki=Ni.Lemma 5.
For eachi∈0,1,…,d−1, ki+ki+1≥5.Proof.
Note that sinceG is 5-edge-connected, we have kiki+1≥5 by Fact 1. Because of this and as a consequence of Fact 3, we obtain ki+ki+1≥5.
The following two lemmas follow immediately from Lemma5.Lemma 6.
Fori∈1,2,…,d−1, if ki=1, then ki−1+ki+ki+1≥9.Lemma 7.
Fori∈1,2,…,d−1, if ki=2, then ki−1+ki+ki+1≥8.Lemma 8.
Fori∈1,2,…,d−1, if ki≥3, then ki−1+ki+ki+1≥8.Proof.
There are two cases to consider.Case 1. There exists an edge, ab∈E, such that a,b∈Ni.SinceG is triangle free, the effect of this is that a and b share no neighbors, that is to say, Na∩Nb=∅. Note that Na∪Nb⊆Ni−1∪Ni∪Ni+1 and Na,Nb≥δ≥λ=5. Hence, ki−1+ki+ki+1≥Na∪Nb=Na+Nb≥5+5=10.Case 2. There are no adjacent vertices in Ni.Leta∈Ni. Since there are no adjacent vertices in Ni, we see that Na∩Ni=∅. Also, Na⊆Ni−1∪Ni+1 and Na≥δ≥λ=5. Hence, ki−1+ki+ki+1≥Ni∪Na=Ni+Na≥3+5=8.Lemma 9.
For eachi∈1,2,…,d−1, ki−1+ki+ki+1≥8.Proof.
There are three cases to consider.Case 1. ki=1.If this is so, then we are done by Lemma6.Case 2. ki=2.If this is so, then we are done by Lemma7.Case 3. ki≥3.If this is so, then we are done by Lemma8.
Throughout the rest of this paper we definec∈0,1,2 as a number such that d−c≡2mod3 where d=diamG.
The following theorem provides a tight upper bound on the diameter of a 5-edge-connected triangle-free graph of prescribed order.Theorem 6.
LetG be a 5-edge-connected triangle-free graph of order n. Then,(24)diamG≤3n−38.
This inequality is, apart from an additive constant, best possible.Proof.
Note thatn=∑i=0dki=∑i=0d−c−2/3k3i+k3i+1+k3i+2+kd−c+1+kd−c+2 where ki=0 whenever i>d. Hence, there are three cases to consider.Case 1. d≡0mod3. If this is so, then c=1, and we have the following by Lemma 9 and the fact that kd≥1 since Nd is nonempty:(25)n=∑i=0dki=∑i=0d−1−2/3k3i+k3i+1+k3i+2+kd≥∑i=0d−3/3k3i+k3i+1+k3i+2+kd≥∑i=0d−3/38+1=d−33+18+1=8d3+1,and makingd subject of the formula, we obtain d≤3n−3/8.Case 2. d≡1mod3. If this is so, then c=2, and we have the following by Lemma 9 and Lemma 5:(26)n=∑i=0dki=∑i=0d−2−2/3k3i+k3i+1+k3i+2+kd−1+kd≥∑i=0d−4/3k3i+k3i+1+k3i+2+kd−1+kd≥∑i=0d−4/38+5=d−43+18+5=8d−83+5,and makingd subject of the formula, we obtain d≤3n−7/8.Case 3. d≡2mod3. If this is so, then c=0, and we have the following by Lemma 9:(27)n=∑i=0dki=∑i=0d−0−2/3k3i+k3i+1+k3i+2≥∑i=0d−2/3k3i+k3i+1+k3i+2≥∑i=0d−2/38=d−23+18=8d+83,and makingd subject of the formula, we obtain d≤3n/8−1.
Hence, considering all three cases, we obtaind≤3n−3/8 as desired. To show that this bound is tight, consider the graph Pdπ0,π1,…,πd with all the same properties as before, except that(28)πi=1,ifi=0ord,5,ifi=1ord−1,4,ifi=2ord−2,2,ifi≡0mod3,3,ifi≡1or2mod3.
Observe that wheneverd≡2mod3, diamPdπ0,π1,…,πd=3n−20/8.
The following corollary to Theorem6 follows from the fact that every bipartite graph is also triangle free and the observation that the corresponding extremal graph for the same theorem is bipartite.Corollary 5.
LetG be a 5-edge-connected bipartite graph of order n. Then,(29)diamG≤3n−38.
This inequality is, apart from an additive constant, best possible.
Our final result is a tight upper bound on the diameter of a 5-edge-connected bipartite graph with respect to its size. To obtain the said bound, we need the following definitions and lemmas. LetG be a 5-edge-connected bipartite graph of size m and diameter d>1. Let x,y∈V be fixed vertices in G such that dx,y=diamG=d and let Ni=v∈VdGx,v=i for any 0≤i≤d and ki=Ni. For j<l, let Mj,l=e∈Ee∈E∪i=jlNi,∪i=jlNi for any 0≤j≤d−1 and mj,l=Mj,l. Also, let Mj,l=Mj,l−ENj,Nj∪ENl,Nl and mj,l=Mj,l. Mi is simply the set of edges between vertices in the same distance layer, that is to say, Mi=ENi,Ni, and the cardinality of the same set is given by mi=Mi.Lemma 10.
For eachi∈0,1,…,d, Mi is empty.Proof.
The desired conclusion follows from the assumption thatG is bipartite.Lemma 11.
For eachi∈1,…,d−1, if ki+1+ki+2≥6, then mi,i+3≥21.Proof.
Note that, by Lemma10, Mi=∅. Since ki+1+ki+2≥6, choose any six vertices from Ni+1∪Ni+2. Label the set of vertices we have chosen from Ni+1 as Ni+1′ and the set of vertices we have chosen from Ni+2 as Ni+2′. Identify the edges incident to vertices in Ni+1′ and Ni+2′ as EINi+1′ and EINi+2′, respectively. Note that mi,i+3≥EINi+1′∪EINi+2′=EINi+1′+EINi+2′−EINi+1′∩EINi+2′. Observe that since Ni+1′+Ni+2′=6 and since δ≥λ≥5, we have, by Lemma 10, that EINi+1′+EINi+2′≥∑x∈Ni+1′∪Ni+2′degx≥6δ=30. Since Ni+1′∩Ni+2′=∅ and using the AM-GM inequality, we observe that EINi+1′∩EINi+2′=ENi+1′,Ni+2′≤Ni+1′Ni+2′≤Ni+1′+Ni+2′/22=9. Hence, mi,i+3≥EINi+1′∪EINi+2′=EINi+1′+EINi+2′−EINi+1′∩EINi+2′≥30−9=21, and we are done.
The following fact stems from Lemma5 and the observation that every bipartite graph is also triangle free.Fact 4.
For eachi∈0,1,…,d−1, ki+ki+1≥5.
Fori∈1,2,…,d−3, let S be an induced subgraph of G such that VS=∪j=ii+3Nj. We then have the following useful definition.Definition 1.
S is a scant subgraph of G (or simply, S is scant) if mi,i+3<21.Lemma 12.
IfS, where VS=∪j=ii+3Nj, is scant, then ki+1,ki+2=2,3 or ki+1,ki+2=3,2.Proof.
ByFact 4, Lemma 11, and by the condition of the current lemma, we have that ki+1+ki+2=5. Hence, ki+1,ki+2∈1,4,2,3,3,2,4,1, and it is sufficient to prove the current lemma if we can show that ki+1,ki+2≠1. Suppose to the contrary that ki+1=1. If this is so, then ki+2=4, and since Ni+1∩Ni+2=∅, we obtain ENi+1,Ni+2≤ki+1ki+2=4<5=λ, contradicting the condition that G is 5-edge-connected. The same argument is to be used for the case where ki+2=1, hence settling our lemma.
As a consequence of Lemma12, we further add the following definitions.Definition 2.
LetS, where VS=∪j=ii+3Nj, be a scant subgraph of G. If ki+1,ki+2=2,3, we say S is scant-left, and if ki+1,ki+2=3,2, we say S is scant-right.Lemma 13.
IfS, where VS=∪j=ii+3Nj, is scant, then mi,i+3=20.Proof.
By the condition of the current lemma and by Lemma12, we have that ki+1,ki+2=2,3 or ki+1,ki+2=3,2. Hence, there are two cases to consider.Case 1. ki+1,ki+2=2,3.Note thatmi,i+3≥mi,i+1+mi+1,i+3. Note also that since, by Lemma 10, Mi+2 is empty and since δ≥λ≥5, we have that mi+1,i+3=∑x∈Ni+2degx≥δki+2=15. Further, observe that Mi,i+1 is a disconnecting set of G, and hence mi,i+1≥λ=5. Thus, we have mi,i+3≥mi,i+1+mi+1,i+3≥5+15=20.Case 2. ki+1,ki+2=3,2.We can get the desired conclusion by arguing as in case 1.Lemma 14.
(a)
IfS, where VS=∪j=ii+3Nj, is scant-left, then mi−3,i≥25.(b)
IfS, where VS=∪j=ii+3Nj, is scant-right, then mi+3,i+6≥25.Proof.
We will show that the result holds for (a) as it follows analogously for (b).
(a)ki+2=3 by the condition of the lemma, and hence we have that mi+1,i+3≥∑x∈Ni+2degx≥δki+2=15. Also, mi,i+3≤20, by the condition of the lemma. Hence, mi,i+1≤mi,i+3−mi+1,i+3≤20−15=5. Note that by the condition of the lemma and by Fact 4, we have ki≥3. If each vertex in Ni is adjacent to both vertices in Ni+1, then mi,i+1≥kiki+1≥2ki≥6 which contradicts our deduction that mi,i+1<6. Hence, there is at least one vertex, say a, in Ni which is adjacent to at most one vertex in Ni+1. By Lemma 10 and since dega≥δ≥λ≥5, we see that a has at least four neighbors in Ni−1, that is to say, ki−1≥4. Note that mi−3,i≥mi−3,i−2+mi−2,i. Note also that since, by Lemma 10, Mi−1 is empty and since δ≥λ≥5, we have that mi−2,i=∑x∈Ni−1degx≥δki−1≥20. Further, observe that Mi−3,i−2 is a disconnecting set of G, and hence mi−3,i−2≥λ=5. Thus, we have mi−3,i≥mi−3,i−2+mi−2,i≥5+20=25.
Throughout the remainder of this paper, we assume thatdiamG=d≡cmod3, c∈0,1,2, and we define the set I=0,1,…,d−c−3/3. For p∈I, we define Sp=∪j=3p3p+3Ni. As a result of the previous lemma, we have the following definition.Definition 3.
Forp∈I, we say Sp is a surplus subgraph of G (or simply, Sp is a surplus) if m3p,3p+3≥25.Lemma 15.
m0,d−c≥21I.Proof.
We have three cases to consider.Case 1. For all p∈I, Sp is not scant.If this is so, thenm0,d−c≥∑p∈Im3p,3p+3≥21I and we are done.In the remaining two cases, we assume that for at least onep∈I, Sp is scant. Let A=pjj∈1,2,…,α and B=qjj∈1,2,…,β such that Sp is a left-scant whenever p∈A and Sp is a right-scant whenever p∈B.Case 2. α≥β.If this is so, we have the following. LetC1=p−1p∈A; then, by Lemma 14, Sp is a surplus whenever p∈C1⊂I. Also, let D1=I−A∪B∪C1. Notice that C1=A and since A, B, and C1 are mutually exclusive sets, we have D1=I−A−B−C1=I−2A−B. Further, since α≥β, we have that 3A−B>0. Hence, we obtain m0,d−c≥∑p∈Im3p,3p+3=∑p∈D1m3p,3p+3+∑p∈Am3p,3p+3+∑p∈Bm3p,3p+3+∑p∈C1m3p,3p+3 ≥20A+20B+25C1+21D1=20A+20B+25A+21I−2A−B=21I+3A−B≥21I and we are done.Case 3. α<β.We can get the desired conclusion by arguing as in case 2.
Our final theorem below provides a tight upper bound on the diameter of a 5-edge-connected bipartite graph of prescribed size.Theorem 7.
LetG be a 5-edge-connected bipartite graph of size m. Then,(30)d=diamG≤m+47.
This inequality is, apart from an additive constant, best possible.Proof.
There are three cases to consider.Case 1. d≡0mod3.If this is so, thenc=0 and(31)m=m0,d≥∑p∈Im3p,3p+3≥21I=21d−33+1=7d.Makingd subject of the formula, we get d≤m/7.Case 2. d≡1mod3.If this is so, thenc=1 and(32)m=m0,d≥∑p∈Im3p,3p+3+md−1,d≥21I+5=21d−1−33+1+5=7d−2.Makingd subject of the formula, we get d≤m+2/7.Case 3. d≡2mod3.If this is so, thenc=2 and(33)m=m0,d≥∑p∈Im3p,3p+3+md−2,d−1+md−1,d≥21I+5+5=21d−2−33+1+10=7d−4.Makingd subject of the formula, we get d≤m+4/7. To show that this bound is tight, consider the extremal graph given in Theorem 6. Observe that whenever d≡0mod3, diamPdπ0,π1,…,πd=m/7.


## 3. Conclusion

In this paper, we provided tight upper bounds for bipartite graphs with respect to order and with respect to size for any value ofλ. We also provided tight upper bounds for triangle-free graphs with respect to order for any value of λ. Also, for triangle-free graphs, with respect to size, we provided tight upper bounds for any value of λ where λ≠5. For λ=5 with regard to the size of triangle-free graphs, we provide the following conjecture.Conjecture 1.
LetG be a 5-edge-connected triangle-free graph of size m. Then,(34)d=diamG≤m+47.
Further, if bound Conjecture1 is correct, it would also be asymptotically tight. This is so since this bound almost matches the diameter of the extremal graph in Theorem 7, which is also 5-edge-connected and triangle free, except for a small constant.



---

*Source: 8982474-2020-09-03.xml*