Distance-Regular Graphs of Valency 6 and a 1 = 1

Distance-Regular Graphs of Valency 6 and a ₁ = 1

AKIRA HIRAKI hiraki@cc.osaka-kyoiku.ac.jp

Division of Mathematical Sciences, Osaka Kyoiku University Kashiwara, Osaka 582-8582, Japan

KAZUMASA NOMURA nomura@tmd.ac.jp

College of Liberal Arts and Sciences, Tokyo Medical and Dental University, Kounodai, Ichikawa, 272-0827 Japan

HIROSHI SUZUKI^∗ hsuzuki@icu.ac.jp

Department of Mathematics, International Christian University, Mitaka-shi, Tokyo 181-8585, Japan Received April 3, 1997; Revised October 19, 1998

Abstract. We give a complete classification of distance-regular graphs of valency 6 and a1=1.

Keywords: distance-regular graph, association scheme, P-polynomial scheme

1. Introduction

In this paper we only consider undirected finite graphs without loops or multiple edges. Let 0be a connected graph. We identify0with the set of vertices. For two verticesα, β, let

∂(α, β)denote the usual distance betweenαandβin0. Let 0i(α)= {β ∈0|∂(α, β)=i} and 0(α)=01(α).

0is said to be distance-regular if the cardinality of the set Dⁱ_j(α, β)=0i(α)∩0j(β) for every i,j

depends only on the distance betweenαandβ. In this case we write p_{i j}^m= ¯¯Dⁱ_j(α, β)¯¯,

where m =∂(α, β). Let d = d(0)denote the diameter, i.e., the maximal distance of0, and

ki =p⁰_ii= |0i(α)|.

∗This research was partially supported by the Grant-in-Aid for Scientific Research (No.09640062), the Ministry of Education, Science and Culture, Japan.

r(0)=l(c1,a1,b1).

The girth of0, denoted by g, is the length of a shortest circuit. In particular, the girth g equals 3 if and only if a16=0 for a distance-regular graph0.

Information about general theory of distance-regular graphs is given in [1, 5, 8].

In this paper we prove the following theorem.

Theorem 1.1 Let0be a distance-regular graph of valency 6 and a1 =1. Then one of the following holds.

(1) 0is isomorphic to the collinearity graph of the generalized quadrangle of order(2,2). (2) 0is isomorphic to the collinearity graph of one of the two generalized hexagons of

order(2,2).

(3) 0'H(3,3),the Hamming graph 3³.

(4) 0is isomorphic to the 3-cover of the collinearity graph of a generalized quadrangle of order(2,2),the halved Foster graph.

In [12] A.A. Ivanov proved that the diameter d(0) of a distance-regular graph0 is bounded by a function of the valency k and r(0). So in order to classify distance-regular graphs of fixed valency k, the major part of work is to give an upper bound of r(0). On the other hand if r(0)≥2, it is easy to see that every maximal clique has size s+1=a1+2.

In particular, t+1=k/(a1+1)is an integer. So we define the following.

A distance-regular graph0is said to be of order(s,t)if0(α)'(t+1)·Ksfor every vertexα. If0does not have an induced subgraph isomorphic to K2,1,1, then a distance- regular graph0is of order(s,t)for some s and t . In particular, this is the case if r(0) >1 or a₁≤1. In this terminology this paper is concerned with a classification of distance-regular graphs of order(2,2).

Let0be a distance-regular graph of order(s,t). If t =0, it is clear that0is a complete graph.

If t =1,0is a line graph and we have a classification of such graphs. See [8, 13] and Proposition 6.2.

We are interested in the next case, t =2. If s =1, i.e., a1=0 then k=3. A classification of distance-regular graphs of valency 3 is completed by Ito [11], Biggs–Boshier–Shawe- Taylor [6] and Bannai–Ito [3]. In this paper we treat the case s =t =2. It seems that the situation is a little different in each of the following cases.

t <s, t =s and t>s.

Actually, stimulated by our result and the techniques developed in this paper, N. Yamazaki proved the following [16].

Theorem 1.2 Let0be a distance-regular graph of order(s,2)with s>2. Then one of the following holds.

(1) d(0)≤r(0)+2.

(2) 0is a bipartite half of a distance-biregular graph with vertices of valency three.

We note here that the condition s >2 is essential in his proof. We believe that our case is one of the key parts of the classification of distance-regular graphs with t =2.

We also note that k =6,a₁=1 is the smallest unsettled case with girth equals 3.

For the convenience of the reader, we also give a classification of distance-regular graphs of valency k≤7,girth 3 in the last section. Except the case k=6,a₁=1, the results may be known to some specialists.

In [15], the third author called a distance-regular graph extra thin if b₁ =c_d−1. If an extra thin distance-regular graph satisfies ad 6=0, then k=ad(ad+1)and a1=ad−1. So Theorem 1.1 includes the nonexistence of extra thin distance-regular graphs with ad =2.

Our proof is divided into two parts.

In the first part we apply combinatorial arguments to show that either d(0)≤r(0)+2 or 0is a bipartite half of a bipartite distance-regular graph of valency 3. We use intersection diagrams and investigate the clique patterns on the diagram of rank 1. (See the last part of Section 2.) After determining the clique patterns, we apply circuit chasing techniques. See Sections 3 and 4.

Since bipartite distance-regular graphs of valency 3 are completely classified [11], in the second part we assume d(0)≤r(0)+2. We use eigenvalue techniques. We follow mainly the techniques developed by E. Bannai and T. Ito [2–4]. Using additional information in our case and refinement in computation, we could obtain a bound r(0)≤17. Now it is not hard to determine the feasible arrays either by computer testing the integrality condition of multiplicities of eigenvalues, or by hand checking the divisibility condition coming from the number of circuits of certain types.

We also note here the importance of these two parts. Under our assumption, it is not hard to show that if l(c,a,b)≥2, then(c,a,b)=(1,1,4),(2,2,2)or(4,1,1). By a result of E. Bannai and T. Ito in [2], l(2,2,2)≤10·6·2⁶. Now we can apply the main theorem in [4] and d(0)is bounded. So in this sense, d(0)is theoretically bounded. In order to get a complete classification, however, we need to obtain a reasonable upper bound of d(0). For that reason, it was essential to show that d(0)≤r(0)+2.

Our notation and terminologies are standard except the following.

Let e(A,B)denote the number of edges between subsets A, B of0. Instead of e({x},B), we will write e(x,B).

For an edgeα∼β,

D(α, β)=D₁¹(α, β)=0(α)∩0(β).

Let u, vbe vertices at distance i . We call the induced subgraph on0i−1(u)∩0(v), the c_i-graph or the c_i-graph0i−1(u)∩0(v). The b_i-graph and the a_i-graph are defined similarly.

Lemma 2.2 [8,Lemma 5.5.2] Let0be a distance-regular graph and let 2≤i ≤d−1.

Suppose that for all verticesα, β with∂(α, β)=i+1,the c_i+1-graph0i(α)∩0(β)is a clique. Then c_i+1=1.

Lemma 2.3 Let0be a distance-regular graph with k =6,a₁ =1. If b_d−1 =1,then one of the following holds.

(1) c_d =6 and k_d−1≡0(mod 3). (2) cd =4 and kd ≡0(mod 3).

Proof: If cd =6, the assertion is obvious.

Suppose cd 6=6, i.e., ad 6=0. Let∂(u, v)=d and Dⁱ_j=0i(u)∩0j(v). Since bd−1=1, e(D^d₁⁻¹,D^d₁∪D^d₂)=0. See figure 1. So a subgraph D₁^d−1is 1-regular and c_d≡0(mod 2). If cd =2, the cd-graph D^d₁⁻¹is a clique. This contradicts Lemma 2.2. Hence cd =4=b1. So e(D^d₁,D^d₂)=0. This implies that every connected component of0d(α)is a clique of

size 3. Thus kd ≡0(mod 3). 2

Proposition 2.4 [9] Let0be a distance-regular graph of valency k,a = a₁ 6= 0. Let r=r(0). Suppose

(cr+1,ar+1,br+1)= · · · =(cr+t,ar+t,br+t)=(2,2a,b).

Then t ≤1.

Figure 1. Rank d diagram with bd−1=1.

In this and the following two sections we will use intersection diagrams of rank 1. For intersection diagrams, see for example [7, 9].

Lemma 2.5 Let0be a distance-regular graph of order(s,t)and r =r(0). For every pair of verticesαand x with∂(α,x)=r+1,the cr+1-graph0r(α)∩0(x)is a coclique.

Proof: We may assume that cr+1 ≥ 2. Take any y1,y2 ∈ 0r(α)∩0(x). Let{β} = 0(α)∩0r−1(y₁).

The intersection diagram with respect to(α, β)has the following shape. (See [9].) In particular, we have e(D_r^r+1,D_r^r)=0.

Note that y₁∈D_r^r₋₁and x ∈ D_r^r+1. Since 1=c_r =e¡

x,D_r^r₋₁¢

= |{y₁}|,

y₂must be in D_r^r₊₁. Hence we have y₁6∼y₂. 2

Let0be a distance-regular graph with k =6,a₁ =1, and r =r(0). Then for each vertex x ∈ 0,0(x)= 3·K₂, i.e., a disjoint union of three K₂’s. We fix the following notation in this and the following two sections.

∂(α, β)=1, Dⁱ_j =0i(α)∩0j(β), D₁¹= {γ}.

Note that|D₁¹| =1 as a1=1.

We introduce three terms which play key role in the following sections. They are ‘clique type’, ‘vertex type’ and ‘clique pattern’. Let x = {ζ, η, ξ}be a clique. By the clique type (with respect to a vertexπ) of x, we mean

(∂(π, ζ )−r, ∂(π, η)−r, ∂(π, ξ)−r)

the list of distances fromπminus r of vertices in a clique.

We call

δE=(∂(α, δ)−r, ∂(γ, δ)−r, ∂(β, δ)−r)

the type of a vertexδ (with respect to(α, β)). We also use column vectors in the figures.

The clique pattern atδis the collection of types of vertices in0(δ)with edges among them.

Figure 2. Rank 1 diagram with cr+1>1.

In this section we prove the following.

Theorem 3.1 Let0be a distance-regular graph with k =6,a1 =1. Let r =r(0). If cr+1≥2,then d≤r+2 and one of the following holds.

(1) d =r+1 and cr+1≤3.

(2) (c_r+1,a_r+1,b_r+1)=(2,2,2)and c_r+2=3.

(3) (cr+1,ar+1,br+1)=(2,3,1)and cr+2=6.

Proof: As we remarked in the previous section, for each vertex x ∈0,0(x)'3·K2, i.e., a disjoint union of three K2’s.

Since every cr+1-graph is a coclique by Lemma 2.5, cr+1 ≤ 3. Moreover if cr+1 =3, then br+1=0, i.e., d=r+1. Hence we may assume that cr+1=2 and br+1≥1 to prove our theorem.

Take any edge x ∼ y with x ∈ 0r+1(α) and y ∈ 0r+2(α). Since cr+1 = 2, we have {z1,z2} = 0r(α)∩0(x). We have z1 6∼ z2 by Lemma 2.5. Hence{wj} = D(x,zj)

⊂0r+1(α)for j=1,2. This means br+1≤2.

Case 1. br+1=2, i.e.,{y⁰} =D(x,y)⊂0r+2(α).

The types of cliques in0(x)∪ {x}for each x ∈0r+1(α)are as depicted in figure 3.

Figure 3. Clique types of x∈0r+1(α)with cr+1>1.

This implies that every cr+2-graph is a coclique. Hence we have cr+2≤3. Moreover, if cr+2=3, then d=r+2, we have (2).

Suppose c_r+2=2. Then e(D^r_r⁺₊₁²,D^r_r⁺₊₂¹)=0 and by Proposition 2.4, b_r+2 6=2. So we have an edge y∼u with y∈ D_r^r+₊²₁and u∈D_r^r₊⁺₂².

Suppose there exists a vertexv∈0(u)∩D_r^r₊⁺₁¹. Sinceα, β∈0r+1(v), we haveγ ∈0r(v) from figure 3. This means that∂(u, γ )=r+1. Moreover,α∈0r+2(y)andβ∈0r+1(y) impliesγ ∈0r+2(y). Hence

D^r_r+⁺₂¹(γ, β)3u∼y∈ D^r_r⁺₊²₁(γ, β).

This is a contradiction.

On the other hand suppose e(u,D^r_r⁺₊₁¹)= 0. Then0(u)∩(D_r^r₊⁺₂¹∪ D^r_r⁺₊₁²)is a union of two cocliques of size 2 without edges in between, because it contains two cr+2-graphs 0r+1(α)∩0(u)and0r+1(β)∩0(u), and e(D^r_r⁺₊²₁,D^r_r⁺₊¹₂) = 0. Hence 0(u)contains a coclique of size 4, a contradiction. Thus we have (2) in this case.

Case 2. br+1=1, i.e.,{y⁰} =D(x,y)⊂0r+1(α).

The types of cliques in0(x)∪ {x}for each x∈0r+1(α)are as depicted in figure 3.

This implies that every cr+1-graph is a coclique of size 2 and every cr+2-graph is a union of K2’s. If cr+2=6, we have(3). Hence we may assume that cr+2=4, as every cr+2-graph always contains a cr+1-graph as a subgraph.

Letδ ∈ D_r^r₊⁺¹₁. Since α, β ∈ 0r+1(δ), we haveγ ∈ 0r(δ)∪0r+2(δ)from figure 3.

Moreover, D^r_r+⁺₁¹∩0r+2(γ )6= ∅, for example every vertex in0r+1(α)∩0r+2(γ )satisfies this condition. Note thatδ ∈ D_r^r₊⁺₁¹∩0r+2(γ ), i.e., δ is of type(1,2,1), if and only if e(δ,D_r^r)=0.

Take a vertex x of type (1,2,1). Let {z1,z2} = 0(x)∩ D_r^r₊₁, {z⁰₁,z⁰₂} = 0(x)∩ D_r^r+1with z1∼z⁰₁, z2∼z⁰₂.

Now we apply a circuit chasing technique.

Take a circuit x0∼x1∼ · · · ∼x2r+2∼x0of length 2r+3 such that x₀∈ D₁⁰, x_i∈ Dⁱ_i−1, i =1, . . . ,r+1, x_r+1=z⁰₂

x=x_r+2∈ D_r^r₊⁺₁¹, x_r+j∈ D^r_r⁺₊₄³₋⁻_j^j, j =3, . . . ,r+2, x_r+3=z₁.

Let{yi} = D(xi,xi+1).We have y0 =γ,yr+1 =z2,yr+2 =z⁰₁, and this circuit does not contain a triangle, i.e., xi6∼xi+2. See figure 4.

Changing the base points to x1,x2, we have easily that x_r+2∈ D_r^r+1, x_r+3∈ D_r^r₊⁺¹₁, x_r+4∈ D_r^r₊₁.

Since∂(x1,yr+2)=r,yr+2 ∈D^r_r+1. Since{xr+4,yr+2} ⊂D^r_r+1∩0(xr+3), e(xr+3,D_r^r)= 0. This implies that xr+3∈0r+2(y1)and it is of same type as x. In particular,∂(x2,yr+3)= r . By induction we have that

r=∂(xr+2,y0)=∂(x,y0)=r+2.

Figure 4. Circuit of length 2r+3.

This is a contradiction.

This completes the proof of Theorem 3.1. 2

Remark

1. For Case 2, our original proof was different. We showed that if d ≥r+2,0is a bipartite half of a bipartite distance-regular graph of valency 3. (See(cr+1,ar+1,br+1)=(1,3,2) case in the next section.) The above proof was suggested by N. Yamazaki.

2. Case (3) in Theorem 3.1 does not occur. Actually, we could eliminate this case. However we decided to eliminate this case after bounding the diameter in Section 5 to avoid lengthy arguments.

4. The case c_r+1 =1

In this case we prove the following.

Theorem 4.1 Let0be a distance-regular graph with k =6,a₁ =1. Let r =r(0). If cr+1=1,then one of the following holds.

(1) d =r+1.

(2) d =r+2, ar+1=4, cr+2=6.

(3) d =r+2, ar+1=3, cr+2=3 or 4.

(4) d =r+2, ar+1=2, cr+2=2,3 or 4.

(5) 0is a bipartite half of a bipartite distance-regular graph of valency 3.

Proof: Throughout this proof we assume that d≥r+2. First we note that e(D^r_r+1,D_r^r+1)= 0 as cr+1=1. By Proposition 2.1, there is a cr+2-graph, which is not a coclique. In partic- ular cr+2≥2. We argue three cases separately depending on the values of ar+1.

The following are the clique types of vertices in0(x)∪ {x}for each x ∈0r+1(α).

Figure 5. Clique types of x∈0r+1(α)with cr+1=1.

Case 1. a_r+1=4.

By figure 5, it is easy to see that every c_r+2-graph is a union of K₂’s, and therefore c_r+2 ∈ {2,4,6}. c_r+2 =2 is impossible by Lemma 2.2. We want to show that c_r+2 =6.

So we will assume cr+2 =4 to derive a contradiction.

Step 1. D^r_r⁺₊²₁∪D^r_r⁺¹∪D_r^r₊₁∪D^r_r⁺₊₂¹⊂0r+1(γ ).

Since{α, β, γ}is a clique, the assertion follows easily from figure 5.

Step 2. e(D_r^r₊⁺₁²,D_r^r₊⁺₂¹)=0.

We may assume d = r +2, as otherwise b_r+1 = b_r+2 = 1 and the assertion is obvious. Suppose there exists an edge z ∼z⁰such that z ∈ D_r^r+₊²₁ and z⁰ ∈ D_r^r₊⁺₂¹. Let {y} = D_r^r+1 ∩0(z). Since cr+1 = br+1 = 1, {y⁰} = D(z,y) ⊂ D_r^r+₊¹₁ and{x} = D(z,z⁰)⊂ D^r_r+⁺₁¹. Hence the clique pattern at z is as in figure 6. Consider the clique pattern at x. Then there are adjacent vertices w, w⁰ in0(x) both of type (1, 1, 1).

Hence the clique pattern atwis as in figure 6. Then0(w)∩0r+2(γ )= ∅by Step 1, a contradiction.

Step 3. Let u ∈ D_r^r₊⁺₁¹ such that∂(u, γ )≥ r+1. Then there are three possible clique patterns. See figure 7.

Let{v} = D^r_r⁺¹∩0(u), {v⁰} = D_r^r₊₁∩0(u).

Suppose{w} = D(u, v)⊂D_r^r+₊²₁. Then there exists a vertexw⁰∈0(u)∩D_r^r₊⁺¹₂. Since br+1 =cr+1 = 1, the other two vertices x,y in0(u)are in D^r_r+⁺₁¹. Sincewis of type

Figure 6.

Figure 7. Clique patterns of the case ar+1=4.

(2, 1, 1), u cannot be of type (1, 2, 1) by Step 2, as otherwise D^r_r+⁺₁²(α, γ )3w∼u∈ D^r_r⁺₊¹₂(α, γ ).

Hence u is of type (1, 1, 1), and we may assume that E

x =(1,0,1), yE=(1,2,1).

Since y6∼x and y6∼w⁰, x∼v⁰. We have B-type. By symmetry, we have A-type if D(u, v⁰)⊂D^r_r+⁺₂¹.

Now we may assume that D(u, v)∪D(u, v⁰)⊂D^r_r⁺₊¹₁.

Let{x} =D(u, v),{x⁰} = D(u, v⁰). The other two vertices y, win0(u)must lie in D_r^r+₊¹₁ and D^r_r+⁺₂²by Step 2. Since br+1 =1, ∂(w, γ )≥r+2, as otherwise∂(w, γ )=r+1 and

2= |{α, β}| ≤ |0r+2(w)∩0(γ )| =br+1.

We have∂(y, γ )≥ r+1. HenceuE =(1,2,1), as otherwise u must be adjacent to a vertex in0r(γ ), which is impossible. Therefore we also havexE= Ex⁰=(1,1,1).

If d ≥r+3, thenwE=(2,3,2), Ey=(1,2,1), and we have C-type.

If d=r+2, thenwE=(2,2,2), Ey=(1,2,1), asyE=(1,1,1)implies br+1≥2.

Step 4. r ≡0 (mod 3).

We apply a circuit chasing technique.

Take a circuit x0∼x1∼ · · · ∼x2r+2∼x0of length 2r+3 such that x₀∈ D₁⁰, x_i ∈ D_iⁱ₋₁, i =1, . . . ,r+1,

x_r+2∈ D^r_r⁺₊₁¹, x_r+j ∈ D_r^r₊⁺³₄⁻₋^j_j, j =3, . . . ,r+2. It is easy to see that with respect to the base points xi,xi+1,

x_i+j ∈ D_j^j₋₁, j =1, . . . ,r+1, x_r+2+i∈ D^r_r+⁺₁¹, xr+i+j ∈ D_r^r₊⁺₄³⁻₋^j_j, j=3, . . . ,r+3,

where the indices of xi’s are taken modulo 2r+3.

Assume that xr+2is of A-type. Let{yi} = D(xi,xi+1).In particular yr+2∈0r+1(x0)∩0r+1(y0)∩0r+2(x1).

Changing the base points to x1,x2, we have yr+2∈ D_r^r₊⁺²₁, as xr+2∈D_r^r+1, xr+3∈ D_r^r₊⁺¹₁, and yr+2∈0r+2(x1).

Hence xr+3is of B-type and yr+3∈0r+2(y1)∩D^r_r+⁺₁¹.

Changing the base points to x2,x3, we have yr+3∈ D_r^r₊⁺¹₁as before.

We claim that yr+3 ∈0r+1(y2). Since yr+3 ∼xr+3 ∈ D^r_r⁺¹, ∂(yr+3,y2)≥r+1. If yr+3∈0r+2(y2), then the br+1-graph0(x2)∩0r+2(yr+3)contains y1,y2. This contradicts br+1=1. Thus yr+3 ∈0r+1(y2)and yr+3is of A-type. So xr+4must be of C-type and yr+4∈0r+1(y2)∩D_r^r₊⁺₁¹.

Changing again the base points to x3,x4, we have yr+4∈ D_r^r₊⁺¹₁. We claim that yr+4∈0r+2(y3). If yr+4∈0r+1(y3), then

x₂,y₂,x₄,y₃∈0r+1(y_r+4)∩0(x₃)

Figure 8. Circuit of length 2r+3.

form 2·K₂. This is impossible by figure 5. Hence y_r+4 ∈0r+2(y₃)and x_r+5is of A-type.

We have proved that the type changes A→ B→C→ A

with period 3, as we change the base points successively in this circuit. Thus we can conclude that 2r+3≡0 (mod 3).

Step 5. The case c_r+2=4 is not possible.

In the following, we show that r ≡1 (mod 3) to derive a contradiction.

Take a circuit x₀∼x₁∼ · · · ∼x_2r+3∼x₀of length 2r+4 such that x₀∈ D₁⁰, x_i ∈ D_iⁱ₋₁, i =1, . . . ,r+2,

x_r+3∈ D^r_r⁺₊₁¹, x_r+j ∈ D_r^r₊⁺⁴₅⁻₋^j_j, j =4, . . . ,r+3.

Assume that xr+3is of A-type. We note that this circuit does not contain triangles. Let {y_i} =D(x_i,x_i+1).

Changing the base points to x₁,x₂, we have x_r+3∈ D_r^r₊⁺¹₁, and∂(x_r+3,y₁)≥r+1.

If∂(x_r+3,y₁)=r+1, then we can argue as before and conclude that0r+1(x_r+3)∩0(x₁) 3x₀,y₀,x₂,y₁is an a_r+1-graph containing 2·K₂, which is a contradiction. Hence x_r+3 is of C-type and y_r+2∈0r+1(y₁). Moreover y_r+3∈ D^r_r⁺₊²₂, as y_r+3∈0r+2(x₁)∩0(x_r+3), and we have xr+4∈0r+2(y1)∩D_r^r₊⁺₁¹.

Changing the base points to x₂,x₃, we have x_r+4 ∈ D_r^r₊⁺¹₁, and y_r+3 ∈ D_r^r₊⁺²₁. Hence xr+4is of B-type. Since xr+5∈ D¹₁(xr+4,xr+6), and xr+46∼xr+6, we have xr+5∈ D^r_r⁺₊₂¹. Changing again the base points to x₃,x₄, we have x_r+5 ∈ D^r_r⁺₊₁²,x_r+6 ∈ D_r^r₊⁺₁¹ by Step 2. Since xr+46∼xr+6,xr+6is not of B-type. Thus xr+6is of A-type.

Figure 9. Circuit of length 2r+4.

Hence we have the same profile with respect to x0,x1.

Therefore we conclude that 2r+4≡0 (mod 3). This contradicts Step 4.

Therefore we have (2) in this case.

Case 2. ar+1=3.

In this case, cr+2=2,3,4, or 6.

Suppose cr+2=3, and d≥r+3. If br+2=2, then every br+2-graph is a clique, hence so is every br+1-graph. This is impossible as cr+2 =3.

If b_r+2=1, then we have a contradiction by Lemma 2.3. Hence d ≤r+2, in this case.

Next we treat the case c_r+2 =2.

Lemma 4.2 If(cr+1,ar+1,br+1)=(1,3,2),with cr+2 =2,then e(D_r^r₊⁺¹₂,D_r^r₊⁺²₁)6=0.

Proof: Suppose e(D_r^r₊⁺¹₂,D_r^r₊⁺²₁)=0.

Step 1. Let u∈ D_r^r₊⁺₁¹, v∈ D_r^r+1, andw∈ D^r_r+⁺₁²be a triangle. Then the clique pattern at the vertex u is as in figure 10.

Since c_r+2 =2, e(w,D_r^r₊⁺₁¹)=1 andw ∈ 0r+2(γ ), as otherwisew ∈0r+1(γ )and there would exist a vertex u⁰such that

u 6=u⁰∈0r(γ )∩0(w)⊂D_r^r₊⁺¹₁.

Figure 10. Clique pattern of the case ar+1=3 (1).

Letw⁰⁰ ∈ 0(v)∩D_r^r₊⁺₁² withw⁰⁰ 6= w. Thenw⁰⁰ ∈ 0r+2(γ )as above. Since br+1 = 2 andv ∈ 0r+1(γ ),u ∈ 0r+1(γ ). Hence there is a vertex x ∈ D_r^r₊⁺₁¹∩0(u)∩0r(γ ). Now Step 1 follows immediately.

Step 2. There is no triangle u ∈D^r_r+⁺₁¹, v∈ D^r_r⁺¹, w∈ D^r_r⁺₊₁².

Suppose there exists a triangle{u, v, w}with u ∈ D_r^r₊⁺¹₁, v ∈ D_r^r+1 andw ∈ D^r_r⁺₊₁². Take a circuit x₀∼x₁∼ · · · ∼x_2r+2∼x₀of length 2r+3 such that

x₀∈ D₁⁰, x_i ∈ D_iⁱ₋₁, i =1, . . . ,r+1, x_r+2∈ D^r_r⁺₊₁¹, x_r+j ∈ D_r^r₊⁺³₄⁻₋^j_j, j =3, . . . ,r+2.

Let{yi} = D(xi,xi+1).Suppose u =xr+2, v =xr+1, w = yr+1. So x0 ∈0r+2(yr+1). Then by Step 1, yr+2∈ D^r_r⁺₊¹₂. See figure 11.

Changing the base points to x1,x2, we have that xr+2 ∈D^r_r⁺¹, xr+3 ∈D^r_r+⁺₁¹, and xr+4 ∈ D_r^r₊₁. Since y_r+2 ∈ 0r+2(x₁), y_r+2 ∈ D^r_r⁺₊²₁. Thus again by Step 1, y_r+3 ∈ D_r^r₊⁺¹₂ and x_r+3∈0r+1(y₁).

Figure 11. Circuit of length 2r+3.