Rebuilding convex sets in graphs

Discrete Mathematics 297 (2005) 26–37 www.elsevier.com/locate/disc Rebuilding convex sets in graphs José Cáceresa,1, Alberto Márquezb,2, Ortrud R. Oellermannc,3, María Luz Puertasa,4 aDepartment of Statistics and Applied Mathematics, University of Almeria, Spain bDepartment of Applied Mathematics I, University of Seville, Spain cDepartment of Mathematics and Statistics, The University of Winnipeg, 515 Portage Avenue, Winnipeg, Manitoba, Canada R3B 2E9 Received 17 December 2002; received in revised form 18 June 2004; accepted 1 March 2005 Available online 11 July 2005 Abstract Theusualdistancebetweenpairsofverticesinagraphnaturallygivesrisetothenotionofaninterval betweenapairofverticesin agraph.Thisinturnallowsustoextendthenotionsofconvexsets,convex hull, and extreme points in Euclidean space to the vertex set of a graph. The extreme vertices of a graph are known to be precisely the simplicial vertices, i.e., the vertices whose neighborhoods are complete graphs. It is known that the class of graphs with the Minkowski–Krein–Milman property, i.e., the property that every convex set is the convex hull of its extreme points, is precisely the class of chordal graphs without induced 3-fans.We define a vertex to be a contour vertex if the eccentricity of every neighbor is at most as large as that of the vertex. In this paper we show that every convex set of vertices in a graph is the convex hull of the collection of its contour vertices. We characterize those graphs for which every convex set has the property that its contour vertices coincide with its extreme points.A set of vertices in a graph is a geodetic set if the union of the intervals between pairs of vertices in the set, taken over all pairs in the set, is the entire vertex set. We show that the contour vertices in distance hereditary graphs form a geodetic set. © 2005 Elsevier B.V. All rights reserved. Keywords: Eccentricity; Contour vertex; Distance hereditary graph; Convex hull; Geodetic set E-mail address: [email protected] (O. Oellermann). 1Research supported in part by FQM 164 grant. 2Research supported in part by FQM 305 grant. 3Research supported by an NSERC grant Canada. 4Research supported in part by BFM2001-2474 grant. 0012-365X/$-see front matter © 2005 Elsevier B.V. All rights reserved. doi:10.1016/j.disc.2005.03.020 J. Cáceres et al./Discrete Mathematics 297 (2005) 26–37 27 1. Introduction The study of abstract convexity began in the early fifties with the search for an axiom system that defines a convex set and in some way generalizes the classical concept of a Euclidean convex set. Numerous contributions to this topic have been made. An extensive survey of this subject can be found in [20]. Among the wide variety of structures that have been studied under abstract convexity are metric spaces, ordered sets or lattices and graphs, the last being the focus of this paper. We now give a brief introduction to abstract convexity as it pertains to graphs. Let Vbe a finite set and Ma finite collection of subsets of V.Then Mis an alignment of Vif and only if M is closed under intersection and contains both Vand the empty set. If Mis an alignment of V, then the elements of Mare called convex sets and the pair (V, M)is called an aligned space.IfS⊆V,then the convexhullof S, denoted byCH(S),is the smallest convexset that contains S. Suppose X∈M. Then, x∈Xis an extreme point for Xif X−{x}∈M. The collection of all extreme points of Xis denoted by ex(X).Aconvex geometry on a finite set is an aligned space with the additional property that every convex set is the convex hull of its extreme points. This property is referred to as the Minkowski–Krein–Milman property. Several abstract convexities associated with the vertex set of a graph are well known (see [10]).Their study is of interest in computational geometry and has some direct applications to other areas such as, for example, game theory (see [4]). For graph terminology we follow [14]; except that we use vertex instead of point and edge instead of line. All graphs considered here are connected, finite, simple, unweighted and undirected. The distance between a pair of vertices u, v of Gis the length of a shortest u–vpath in Gand is denoted by dG(u, v) or d(u, v) if Gis clear from context. The interval between a pair u, v of vertices in a graph Gis the collection of all vertices that lie on some shortest u–vpath in Gand is denoted by IG[u, v]or I[u, v]if Gis understood. Intervals in graphs have been studied extensively (see [2,17,18]) and play an important role in the study of several classes of graphs such as the Ptolemaic graphs (see [16]) or block graphs. A subset Sof vertices of a graph is said to be g-convex if it contains the interval between every pair of vertices in S. It is not difficult to see that the collection of all g-convex sets is an alignment of V. We thus refer to the g-convex sets simply as convex sets.A vertex in a graph is simplicial if its neighborhood induces a complete subgraph. It can readily be seen that pis an extreme point for a convex set Sif and only if pis simplicial in the subgraph induced by S. It is true, in general, that the convex hull of the extreme points of a convex set Sis contained in S, but equality holds only in special cases. In [10] it is shown that a graph has the Minkowski–Krein–Milman property if and only if it has no induced cycles of length bigger than 3 and has no induced 3-fan (see Fig. 1). For another more recent and excellent reference text containing material on graph convexity see [6]. If a graph Ghas the Minkowski–Krein–Milman property and Sis a convex set of V (G), then we can rebuild the set Sfrom its extreme vertices using the convex hull operation. Since this cannot be done with every graph, using only the extreme vertices of a given convex set S, it is natural to ask if it is possible to extend the set of extreme vertices of Sto a set that allows us to rebuild Susing the vertices in this extended set and the convex hull operation. In Section 2 we answer this question in the affirmative using the collection of ‘contour vertices’of a set. To this end, let Sbe a set of vertices in a graph Gand recall that 28 J. Cáceres et al./Discrete Mathematics 297 (2005) 26–37 c b v d a Fig. 1. A 3-fan. the eccentricity in Sof a vertex u∈Sis given by eccS(u) =max{d(u, v) :v∈S}and a vertex v∈Sfor which d(u, v) =eccS(u) is called an eccentric vertex for uin S. In case S=V (G), we denote eccS(u) by ecc(u). A vertex u∈Sis said to be a contour vertex of Sif eccS(u)⩾eccS(v) for every neighbor vof uin S. The set of all contour vertices of S is called the contour set of Sand is denoted by Ct(S).IfS=V (G), the subgraph induced by the contour set of Sis called the contour of Gand is denoted by Ct(G). In Section 3 we establish structural properties of contour vertices and characterize those graphs that are the contour of some other graph using a construction similar to the one used in [3]. In order to find the convex hull of a set Sone begins by taking the union of the intervals between pairs of vertices of S, taken over all pairs of vertices in S. We denote this set by IG[S]or I[S], i.e., I[S]={u,v}⊆SI[u, v]and call it the geodetic closure of S. One then repeats this procedure with the new set and continues until, for the first time, one reaches a set Tfor which the geodetic closure is the set itself , i.e., T=I[T]. This then is the convex hull of S. If this procedure only has to be performed once, we say that the set Sis a geodetic set for its convex hull. In general a subset Sof a convex set Tisageodetic set for Tif I[S]=T. The notion of a geodetic set for the vertex set of a graph was first defined in [7]. InSection4wefocusongeodeticsetsin‘distancehereditarygraphs’.Wefirstdiscusshere howthesegraphsarerelatedtothegraphswith the Minkowski–Krein–Milmanproperty and how the results of Section 4 extend results known for the last class. Howorka [15] defined a connected graph Gto be distance hereditary if for every connected induced subgraph Hof Gand every two vertices u, v in H,dH(u, v) =dG(u, v). In the same paper several characterizations for this class of graphs are given. We state here only one of these which we will use in this paper. Theorem 1. A connected graph Gis distance hereditary if and only if every cycle in G of length at least 5has a pair of crossing chords. Further useful characterizations for this class of graphs were established in [1,9,13]. Apartfromhavingelegantcharacterizations,distancehereditarygraphspossessotheruseful properties. It is a class of graphs for which several NP-hard problems have polynomial solutions. For example the Steiner problem for graphs, which is known to be NP-hard (see [11]), can be solved in polynomial time in distance hereditary graphs (see [5,8,12]). Moreover, these graphs are Steiner distance hereditary as was shown in [9]; i.e., the Steiner distance of a set of vertices is the same, in any connected induced subgraph that contains it, as it is in the graph itself. J. Cáceres et al./Discrete Mathematics 297 (2005) 26–37 29 The class of distance hereditary graphs also properly contains the graphs that possess the Minkowski–Krein–Milman property since a graph is chordal without an induced 3-fan if and only if it is a distance hereditary graph without an induced 4-cycle. It was shown in [10] that in a chordal graph every non-simplicial vertex lies on a chordless path between two simplicial vertices. If Gis a chordless graph without an induced 3-fan, then Gis distance hereditary and thus every induced path is necessarily a shortest path. Hence the simplicial vertices for a convex set Sin a graph with the Minkowski–Krein–Milman property is a geodetic set for S. In Section 4 we show that the contour vertices of a distance hereditary graph form a geodetic set for the graph. In [19] it shown that the contour vertices can be used to find minimum Steiner geodetic sets for distance hereditary graphs. 2. The contour set of a graph In this section we will show that the contour set of a convex set Sof vertices in a graph Gcan be used to rebuild the set by finding its convex hull, in the same way that extreme vertices are used in chordal graphs in [10]. Moreover, we characterize those graphs having the property that the extreme vertices and the contour vertices of every convex set coincide. First we show that the contour set of Gcontains all the extreme vertices. Lemma 2. Let Gbe a graph and S⊆V (G).Then Ct(S) contains all extreme vertices of S. Proof. Let u∈Sbe an extreme vertex for S. Then uis a simplicial vertex for S.Wenow show that uis a contour vertex of S. Let vbe a neighbor of uin Sand ve∈San eccentric vertex for vin S, i.e., d(v,ve)=eccS(v). Suppose that d(u, ve)=d(v,ve)−1 and let Pbe a shortest u–vepath. Then the vertex following uon P, say w,isnotv. Since uis simplicial, vand wmust be adjacent. However, then d(u, ve)⩾d(v,ve), a contradiction. So eccS(u)⩾d(u, ve)⩾d(v,ve)=eccS(v) and therefore uis a contour vertex for S. Therelationshipbetweencontourverticesandextremeverticesisevencloserfortheclass of distance hereditary graphs without induced 4-cycles.The next result is a characterization of contour vertices in graphs with the Minkowski–Krein–Milman property that resembles the characterization of simplicial vertices. Proposition 3. Let Gbe a distance hereditary graph without induced 4-cycles. A vertex x∈V (G) is acontour vertexfor Gifand only if eachneighbor vofxwhichis on ashortest path between xand some eccentric vertex for xsatisfies N[x]⊆N[v]. Proof. If Gis complete, the result is immediate. Suppose now that Gis not complete. Then no contour vertex of Gcan have eccentricity 1. So if xis a contour vertex and xeis an eccentric vertex for x, then d(x,xe)⩾2. Let P:(x=)y0y1...y k(=xe)be a shortest x–xe path. Suppose u= y1is a neighbor of x. Then uis not on Pand uP cannot be a shortest u–xepath; otherwise, ecc(u) > ecc(x) which is not possible since xis a contour vertex. Since Gis distance hereditary, the subgraph induced by uand the vertices of Pcontains a 30 J. Cáceres et al./Discrete Mathematics 297 (2005) 26–37 shortest u–xepath. Hence there is a chord between uand some vertex on Pwhose distance from xis less than or equal to 2. If uy1is a chord, then u∈N(y1)as desired. If uis a neighbor of y2, then the 4-cycle xy1y2ux must have a chord. So uy1is an edge and again u∈N(y1). Conversely, suppose that xhas the property that each of its neighbors vwhich is on a shortest path between xand some eccentric vertex for xsatisfies N[x]⊆N[v]. Suppose x has a neighbor ysuch that ecc(x) < ecc(y). Then xlies on a shortest path Pbetween yand an eccentric vertex yefor y.Soyeis also an eccentric vertex for x. By our hypothesis yis a neighbor of the vertex adjacent to xin P−y. This is not possible as Pis a shortest y–ye path. So ecc(y)⩽ecc(x) and xis a contour vertex for G. Remark 4. The above result does not hold for all chordal graphs. Take for example the 3-fanofFig.1. Forthisgraphboththeneighbors, ofeitheroneofthe twosimplicial vertices, lieonsomeshortestpathtoaneccentricvertexbuttheirclosedneighborhoodsarenotequal. However, the converse of the above result holds for all connected graphs G, i.e., if a vertex x∈V (G) has the property that for each neighbor vof xwhichis ona shortestpath between xand some eccentric vertex for x,N[x]⊆N[v], then xis a contour vertex. The following result shows that the convex hull of the contour set of a convex set of vertices in a graph is the entire set, without any restriction on the graph. So this result is similar to the Minkowski–Krein–Milman property and holds for all graphs. Theorem 5. Let Gbe a graph and Sa convex subset of vertices. Then S=CH(Ct(S)). Proof. Suppose,tothecontrary,thatS= CH(Ct(S)).SinceSisaconvexset,CH(Ct(S)) ⊆ S. So, by our assumption, S−CH(Ct(S)) =∅. Let u∈S−CH(Ct(S)) be such that ecc(u)⩾ecc(v) for all v∈S−CH(Ct(S)). Since u/∈Ct(S), there exists a neighbor v of uin Ssuch that eccS(v) > eccS(u) and, by our choice of u, the vertex vbelongs to CH(Ct(S)). Let ve∈Sbe an eccentric vertex for vin S, i.e., d(v,ve)=eccS(v). Note that in this case eccS(ve)⩾eccS(v) > eccS(u) and ve∈CH(Ct(S)). Therefore d(u, ve)⩽eccS(u) < eccS(v) =d(v,ve)and so d(u, ve)+1⩽d(v,ve). Let Pbe a shortest ve–upath in S.Then Pfollowed by the edge uv,isave–vpath whose length is d(u, ve)+1⩽d(v,ve). So it is a shortest path between veand vthat contains u. This contradicts the fact that u/∈CH(Ct(S)). In graphs with the Minkowski–Krein–Milman property, the set of extreme vertices for a convex set Sis minimal in the sense that any extreme point of Sis not in the convex hull of a subset of Sthat does not contain it. Unfortunately the contour set does not share this property in general as can be seen in the example of Fig. 1. In this case the contour is the set {a, b, c, d}, but CH({a,b,d})=CH({a, b, c, d}). However, there are examples where the contour vertices are a minimal set in a similar way that extreme vertices are. In the graph of Fig. 2 with S=V (G), the contour set is Ct(S) ={a, b, c, d}and the convex hull of any proper subset of Ct(S) is a proper subset of S. J. Cáceres et al./Discrete Mathematics 297 (2005) 26–37 31 acbd Fig. 2. Graph with a minimal contour. u w x y v Fig. 3. A dart. We now characterize those connected graphs for which every convex set has the property that its contour vertices coincide with its extreme points. Theorem 6. A connected graph Ghas the property that Ct(S) =ex(S) for all convex sets Sof vertices of Gif and only if Ghas the Minkowski–Krein–Milman property and does not contain a dart as induced subgraph (see Fig. 3). Proof. SupposeGhas the property thatCt(S)=ex(S) for all convexsetsSof verticesofG. Let Sbe any convex set of G.Then we know that Sis the convex hull of its contour vertices. SinceCt(S)=ex(S) itfollowsthatSis also theconvexhull of itsextremevertices.HenceG hastheMinkowski–Krein–Milmanproperty.ThereforeGischordalwithoutinduced3-fans. Hence Gis distance hereditary without induced 4-cycles. Suppose Ghas a dart as induced subgraph.LabeltheverticesofsuchadartasinFig.3.LetXbetheverticesinI[u, v]−{u, v}. Then the subgraph Xinduced by Xis complete; otherwise, Ghas an induced 4-cycle, contradicting the fact that Gis chordal.Also if x∈X, then {u, w, y, x,v} is a connected subgraph of Gand since Gis distance hereditary it contains a shortest w–vpath as well as a shortest y–vpath. Hence wx,yxare edges of G.Sowand yare adjacent to every vertex in X. Since d(w,y) =2, it follows that I[y,w]−{w, y} is a complete graph. Suppose I[w, y]contains vertices not in X∪{u}, say u∈I[w, y]−(X ∪{u}). Then d(u,v)=2. Since Gcontains no induced 4-cyclesI[u,v]−{u,v} is complete. If I[u,v]=X, then there is some vertex rsuch that ur /∈E(G) but ur, rv ∈E(G). Hence uurv is an induced u–vpath of length 3. This contradicts the fact that Gis distance hereditary. Thus S=CH({u, v, w, y, x})=I[w, y]∪I[u, v]. Hence all vertices of Sexcept those in Xare contour vertices of S. This contradicts the hypothesis since uis a contour vertex of Sthat is not an extreme point of S, i.e., uis not simplicial. 32 J. Cáceres et al./Discrete Mathematics 297 (2005) 26–37 For the converse, suppose Ghas the Minkowski–Krein–Milman property and does not contain a dart as induced subgraph. Suppose Sis a convex set that has a contour vertex uthat is not simplicial. Then Sis not complete and uis adjacent with a pair w, y of non-adjacent vertices. Let X=N(u) ∩I[u, v]. Since Ghas the Minkowski–Krein–Milman property it can be shown that Xis complete. So wand ycannot both belong to I[u, v].If r∈(N(u)−I[u, v]), thenrmustbe adjacenttoeveryvertexinXsinceuis acontourvertex of Gand since Gis distance hereditary. So neither wnor ybelongs to X.Ifuu1u2...u e=v is a shortest u–vpath in G, then e⩾2 and neither wnor yis adjacent with u2. Hence {u, w, y, u1,u 2} is isomorphic to a dart, contrary to hypothesis. Thus Ct(S) =ex(S). Characterizing graphs Gfor which Ct(G) =ex(G) appears much more difficult. Any connected graph His an induced subgraph of a graph Gwith this property. To see this, take |V(H)|pairwise vertex disjoint, non-trivial cliques and pair off each vertex of Hin a one-to-one manner with one of these cliques. Now identify each vertex of Hwith exactly onevertexinthecliquethatithasbeenpairedoffwith and let Gbe the resultinggraph.Then Ghas the property that Ct(G) =ex(G). It follows that those graphs for which the contour set and the collection of extreme points coincide can have induced cycles of arbitrarily large order. However, not every graph with this property can be constructed in this manner. Take for example the graph obtained from the 6-cycle v1,v 2,...,v 6,v 1by joining a leaf u1to v1and a leaf u4to v4. Then the resulting graph Ghas the property that Ct(G) =ex(G) but Gis not obtained by the above construction. 3. Graphs with a given contour set Inthissectionwecharacterizethosegraphswhicharethecontourofsomeothergraph.The obviousrelationshipbetweencontourandperipheralverticesallowustousetheconstruction used in [3] to also characterize those graphs that are the contour of some graph. Lemma 7. Let Gbe a connected graph and Ca component of its contour. Then all vertices in Chave the same eccentricity. The following result tells us which graphs are not the contour of any graph. Proposition 8. If His a connected,non-complete graph with radius 1, then His not the contour of any graph. Proof. Let Hbe a connected, non-complete graph with radius 1. Then some vertex u∈ V(H)is a neighbor of every other vertex in H. Since His not complete there are two nonadjacentverticesvandv.SupposethereexistsagraphGsuchthatHisthesubgraphinduced by its contour.Then Gmust be connected, since His connected. So, using Lemma 7, every vertex in Hhas the same eccentricity, say k. Note that ecc(v)⩾2, because dG(v, v)=2, so k⩾2. Let w∈V (G) be such that ecc(u) =d(u, w) =k. Then w/∈Ct(G), since k⩾2. So there exists a neighbor w1of wsuch that ecc(w1)>ecc(w)⩾k. Again w1/∈Ct(G), J. Cáceres et al./Discrete Mathematics 297 (2005) 26–37 33 H1 Hi H k v2vM Fig. 4. A disconnected contour set. because its eccentricity is bigger than k. So there exists a neighbor w2of w1such that ecc(w2)>ecc(w1)>k. This process cannot continue indefinitely since Gis a finite graph. However, then the last vertex picked should be a contour vertex. Since its eccentricity is bigger than kwe have a contradiction.  Suppose that His a graph with radius greater than 1. We now describe a graph Gsuch that its contour is H, using the construction given in [3]. Let Gbe the join of Hand K1. Then every vertex of Hhas eccentricity 2 and the vertex of G−V(H)has eccentricity 1. Hence the vertices of Hare precisely the contour vertices of G. A slightly different construction allows us to obtain a graph with given disconnected contoursetsuchthat the eccentricities of theverticesineverycomponent are givennumbers atleast2.Moreprecisely,letHbeadisconnectedgraphwithcomponents,H1,H 2,...,H k. Let n1,n 2,...,n kbe knatural numbers such that n1=nk=max{n1,n 2,...,n k}and M= max{n1,n 2,...,n k}⩽2min{n1,n 2,...,n k}=2m. Note that these are natural restrictions, because Mwill be the diameter of the graph Gand mwill be greater than or equal to the radius. Then there exists a connected graph Gsuch that His the contour of Gand the eccentricity of every vertex in each component Hiof His equal to ni. To construct such a graph Gwe begin with the path v1v2...v M+1of order M+1. Now replace v1by H1 and vM+1by Hkso that all vertices in H1are neighbors of v2and all vertices in Hkare neighbors of vM. Now, for each i,2⩽i⩽k−1,thereexistsavertexvnionthepathsuchthatitseccentricity is ni−1. We now add Hito the graph and join all the vertices of Hito vni(see Fig. 4). Then ecc(ui)=nifor all ui∈Hi,andCt(G) =H. 4. Contour sets and geodetic sets in distance hereditary graphs In this section we show that the contour vertices of a distance hereditary graph form a geodetic set. It is not difficult to see that a set Sof vertices is a convex set of a distance hereditary graph Gif and only if Sinduces a connected graph and is the union of vertices in blocks of Gminus any collection of simplicial vertices from the subgraph induced by these blocks. The results of this section thus show that the contour vertices of all convex sets in distance hereditary graphs are geodetic sets for such sets.As pointed out in the introduction this may be viewed as an extension of the result which states that the simplicial vertices of convex sets in graphs with the Minkowski–Krein–Milman property are a geodetic set for the convex set. 34 J. Cáceres et al./Discrete Mathematics 297 (2005) 26–37 The next result shows that if Gis a distance hereditary graph, then every vertex has an eccentricvertexthatisacontourvertex.Moreover,ifGsatisfiestheMinkowski–Krein–Milman property and if xis a vertex of G, with ecc(x)⩾2, then every eccentric vertex of xmust be a contour vertex. Lemma 9. (1) If Gis adistance hereditarygraphandx∈V (G),then thereis an eccentric vertex for xthat is a contour vertex. (2) Let Gbe a distance hereditary graph without induced 4-cycles. If x∈V (G) is such that ecc(x)⩾2, then each eccentric vertex of xis a contour vertex of G. Proof. (1) The result holds for all distance hereditary graphs with diameter at most 2. Suppose thus that diam(G)⩾3. Among all eccentric vertices for xlet xebe one with maximum eccentricity. Let P:x=v0v1...v k=xebe a shortest x–xepath. We show xe is a contour vertex. If this is not the case, then xeis adjacent with some vertex uwhose eccentricity exceeds that of xe.Thus ecc(u) > ecc(xe)⩾ecc(x) =k.Soecc(u)⩾3. We may assume ulies on Pand that u=vk−1. Suppose ueis an eccentric vertex for u.Then there is a shortest u–uepath Qthat contains xe. Suppose Q:u=u0u1...u t=uewhere u0=vk−1. Thenu2isnotonP.Also clearly uu2/∈E(G).Theonlyvertexon Pthat u2may be adjacent tois vk−2. Indeed u2vk−2isan edge; otherwise,ecc(x)⩾d(x,u2)>k.Since ecc(vk−1)⩾3, u2must be adjacent to a vertex not on P.Ifu3is adjacent with a vertex of Pit can only be adjacent with vk−3; otherwise, either d(vk−1,u 3)= 3ord(x,vk)= k. However, if u3vk−3 is an edge, we have a 6-cycle vk−3vk−2vk−1vku2u3without crossing chords, which is not possible in a distance hereditary graph. So u3vk−3/∈E(G) and d(v0,u 3)=k. By our choice of xe=vk,3⩽ecc(u3)⩽ecc(vk)<ecc(vk−1).Soecc(vk−1)⩾4 and hence u4is not on P. As before we can argue that the only vertex of Pthat u4is possibly adjacent to is vk−4.If u4vk−4∈E(G),thenasbeforeweobtaina6-cyclevk−4vk−3vk−2u2u3u4vk−4whichhasno crossing chords. So u4vk−4/∈E(G). However, then d(x,u4)=k+1>ecc(x) which is not possible. So u= vk−1. Note uis not adjacent with vk−ifor i⩾3; otherwise, d(x,xe)<k, whichisnotpossible.Alsovk−2u∈E(G);otherwise,we havea contradictiontoourchoice of xe=vk.Ifvk−1u∈E(G), then u2is not on P. Note that in this case u2is adjacent with at most one vertex on P, namely, vk−2.Sou3is not on P.Fori⩾3, uicannot be on Psince in this case either d(x,vk)<k or d(u, ui)<i, both of which cannot happen. Moreover, the only vertex on Pthat uican be adjacent with (if any) is vk−i; otherwise, as in the previous case, we have a contradiction. Ifu3vk−3∈E(G), then vk−3vk−2vk−1vku2u3vk−3 is a 6-cycle without crossing chords. So u3vk−3/∈E(G). In this case u2vk−3∈E(G) and d(x,u3)=k. So by our choice of xe=vk,ecc(u3)⩽ecc(vk)<ecc(u)⩽ecc(ut).So3<t. If u4vk−4∈E(G), then vk−4vk−3vk−2u2u3u4vk−4is a 6-cycle without crossing chords. So u4vk−4/∈E(G). But then d(x,u4)=k+1 contradicting the fact that ecc(x) =k. Hence we may assume vk−1u/∈E(G). If u2= vk−1, i.e., u2is not on P, then at least one of u2vk−2and u2vk−1is an edge of G. If u2vk−2/∈E(G), we have a 5-cycle with out crossing chords. So assume u2vk−2∈E(G). For i⩾3 we may argue, as before, that uiis not on Pand that uiis adjacent to at most one vertex on P, namely, vk−i. But then, as in the previous case, we have a contradiction to the fact that ecc(v) =k. So we may assume vk−1=u2. Clearly, u3= vk−2since d(u, u3)=3= d(u, vk−2). Indeed, for i⩾3, uiis not on Pand uiis adjacent with at most