Steiner distance and convexity in graphs

European Journal of Combinatorics 29 (2008) 726–736 www.elsevier.com/locate/ejc Steiner distance and convexity in graphs J. C´ aceresa,1, A. M´ arquezb, M.L. Puertasa aDepartment of Statistics and Applied Mathematics, University of Almer´ ıa, Spain bDepartment of Applied Mathematics I, University of Sevilla, Spain Received 1 February 2006; accepted 5 March 2007 Available online 12 April 2007 Abstract We use the Steiner distance to define a convexity in the vertex set of a graph, which has a nice behavior in the well-known class of HHD-free graphs. For this graph class, we prove that any Steiner tree of a vertex set is included into the geodesical convex hull of the set, which extends the well-known fact that the Euclidean convex hull contains at least one Steiner tree for any planar point set. We also characterize the graph class where Steiner convexity becomes a convex geometry, and provide a vertex set that allows us to rebuild any convex set, using convex hull operation, in any graph. c 2007 Elsevier Ltd. All rights reserved. 1. Introduction The Steiner tree problem in networks, and particularly in graphs, was formulated quite recently – in 1971 – by Hakimi (see [10]) and Levi (see [13]). In the case of an unweighted, undirected graph, this problem consists of finding, for a subset of vertices A, a minimal-size connected subgraph that contains the vertices in A. Such a subgraph is a tree called a Steiner tree of A. The computational side of this problem has been widely studied, and it is known that it is an NP-hard problem for general graphs (see [12]). Abstract convexity started to develop in the early fifties, with the searching of an axiom system to define a set to be convex, in order to generalize, in some way, the classical concept of Euclidean convex set. These concepts can be found in [15]. Among the wide variety of structures that has been studied under this point of view, such as metric spaces, ordered sets or lattices, we are particularly interested in graphs, where several convexities associated to the vertex set are well-known. E-mail addresses: [email protected] (J. C´ aceres), [email protected] (A. M´ arquez), [email protected] (M.L. Puertas). 1Tel.: +34 950 015 665; fax: +34 950 015 147. 0195-6698/$ - see front matter c 2007 Elsevier Ltd. All rights reserved. doi:10.1016/j.ejc.2007.03.007 J. C´ aceres et al. / European Journal of Combinatorics 29 (2008) 726–736 727 Distance optimization properties of Steiner trees have given a way to define the Steiner distance as a generalization of the usual distance in graphs (see [3]). Following that, in Section 2 we define an abstract convexity in the context of graphs by means of the Steiner distance, and we compare it with other well-known convexities in graphs. Section 3is devoted to studying the relation between Steiner trees and convex hulls in the class of HHD-free graphs, and we prove that any Steiner tree of a vertex set is included in the geodesical convex hull of the set. This result extends the well-known fact that the Euclidean convex hull contains at least one Steiner tree for any planar point set, and relates a polynomially solvable problem, such as the computation of the geodesical convex hull, with a NP-hard problem, the Steiner tree problem in graphs. Finally, in Section 4we characterize the class of graphs where Steiner convexity becomes a convex geometry; that means that every convex set is the convex hull of its extreme points. Just some chordal graphs have this property, so we provide a kind of generalization of it, in the sense of finding a vertex set, bigger than extreme points, that plays the same role in any graph. All graphs considered here are finite, simple, unweighted and undirected. 2. The convexity associated to the Steiner distance There are several well-known definitions of convex vertex sets in graphs, and these convexities are usually defined by means of certain paths. In this fashion, a subset Sof vertices of a graph Gis monophonically (geodesically)convex (see [7]) if Scontains every vertex of any chordless (shortest) path between vertices in S. These sets are called m-convex sets (g-convex sets). The definitions above follow the general scheme of abstract convexities. A family Cof subsets of a set Xis called a convexity (see [15]) on Xif contains the empty set and universal set X, is closed under intersections, and is closed under nested unions; that is, if D⊆Cis non-empty and totally ordered by inclusion, then SDis in C. Note that last property is trivial if Xis a finite set. The elements of Care called convex sets. It is clear that any subset Aof a convex structure is included in a smallest convex set, CHC(A)=T{C∈C:A⊆C}, called the convex hull of A. A point pin a convex set Sis said to be an extreme point if S\ {p}is convex. The preceding definitions correspond to m-convexity and g-convexity in graphs and their convex hulls are denoted by CHmand CHgrespectively. If Gis a connected graph and Ais a subset of vertices of G, then the Steiner distance of A denoted by dG(A)(see [3]) is the size |T|(that is, the number of edges) of a smallest connected subgraph Tof Gthat contains A. Such a subgraph is obviously a tree and is called a Steiner tree of A. Endvertices of any Steiner tree Tof Abelong to A, because an endvertex of Tnot in Acan be removed from the tree in order to obtain a smaller tree. Notice that the Steiner distance is, in some sense, a generalization of the usual distance between vertices, simply by considering that Steiner trees of 2-vertex subsets are shortest paths. In fact, there are a number of usual distance properties, such as being a distance stable graph (see [6,4]) or a distance-hereditary graph (see [11]), and distance invariants, such as eccentricity, radius, diameter, center or median, that have been extended to the Steiner distance (see [4,14]). This suggests us that a convexity can be defined using the Steiner distance in a similar way as usual distance is used to defined g-convexity. Definition 1. Let Gbe a connected graph. A subset S⊆V(G)is said to be St-convex if, for any A⊆S, all vertices in every Steiner tree of Abelong to S. The family of all St-convex sets of V(G)defines a convexity called St-convexity. 728 J. C´ aceres et al. / European Journal of Combinatorics 29 (2008) 726–736 The usual convexities in the vertex set of a graph are path-convexities, defined by a system P of paths. Thus a subset Sof vertices is said to be P-convex if Scontains all vertices on every P-path between all pairs u, v ∈S. This scheme is valid for m-convexity and g-convexity, among some others ones. However Steiner-convexity is defined in a different way, characterized by the use of subsets Aof Swith any cardinality, not just pairs of elements of S. In spite of the different nature of the definitions, we can find a close relation between Stconvexity and geodesic and monophonic convexities. Clearly, any m-convex set is also g-convex but not vice versa in general. So convex hulls satisfy the inclusion relation CHg(S)⊆CHm(S), for any graph Gand any subset S⊆V(G). We will show that the St-convex hull can be properly placed between the two terms of the inclusion above. This relation becomes an equality, between St-convexity and g-convexity, or even between the three convexities, in some special cases. A first approximation to the relation between g-convexity and St-convexity comes from the way the Steiner distance is a generalization of the geodesic distance in a graph, as we will see. On the other hand, the following lemma is the key to relating St-convexity and m-convexity. Recall that a chord on a path Pin a graph Gis an edge of Gjoining nonconsecutive vertices of P. Lemma 2. Let G be a connected graph and let A ⊆V(G). Then every internal point of a Steiner tree of A, is in A or lies on a chordless path between two vertices in A. Proof. Let ube an internal point of a Steiner tree Tof A,u6∈ A, and suppose that it does not lie on any chordless path between two vertices in A. Order the neighbors of uin Tarbitrarily {u1,u2,...,uk}, and for each ui, consider an endvertex ai, which is necessarily in A, such that the path between aiand ucontains ui. Then the path in Tbetween any vertex pair ai,ai+1, 1≤i≤k−1, contains u, and by our hypothesis, it has a chord joining two vertices which leave uin the middle. Finally build a new tree removing from Tthe vertex uand the kedges which are incident with u, and adding the k−1 chords in paths between aiand ai+1, 1 ≤i≤k−1. So this new tree has smaller size than Tand contains all vertices in A, which contradicts the choice of Tas a Steiner tree of A. Now we can formulate the relation between three convex hulls in any graph. Proposition 3. Let G be a connected graph and let S ⊆V(G). Then the following chain of inclusions holds: CHg(S)⊆CHSt(S)⊆CHm(S). Proof. It is clear that CHSt(S)is a g-convex set, since Steiner trees of 2-element subsets of Sare shortest paths. This gives the first inclusion. For the second one, we will show that CHm(S)is a St-convex set. Let A⊆CHm(S)and Tbe a Steiner tree of A; then, using Lemma 2, any vertex in Tis in Aor in a chordless path between two vertices in A. So the vertex set of Tis contained in CHm(S). A whole class of graphs, where the inclusions in the proposition above are equalities, are distance-hereditary graphs. A graph Gis said to be distance-hereditary (see [11]) if each connected induced subgraph Fof Ghas the property that dF(u, v) =dG(u, v) for each u, v ∈V(F). Therefore, in these graphs, the chordless paths between vertices are shortest paths, the geodesic and monophonic convexities coincide, and so also does Steiner convexity. Also, the next example shows that the inclusions are not equalities in general. Example 4. In the graph in Fig. 1, the geodesic convex hull of the subset {a,b,c}comprises the black vertices, the Steiner convex hull comprises the black and white vertices and the monophonic convex hull is the whole set of vertices. J. C´ aceres et al. / European Journal of Combinatorics 29 (2008) 726–736 729 Fig. 1. A graph with non-equal geodesic, Steiner and monophonic convex hulls. 3. St-convexity in HHD-free graphs A graph is called house-hole-domino free (HHD-free) (see [1]) if it contains no induced house, domino, or induced cycle Ck,k≥5. Several types of graphs are contained in the class of HHD- free graphs (see [1]), such as chordal and distance hereditary graphs among others. The relation between geodesic and Steiner convexities becomes an equality in the class of HHD-free graphs. The key to show this relation is the following result that relates Steiner trees of HHD-free graphs with geodesical convex hulls, in a similar way as they are related in the case of the Euclidean plane. For any set Sof vertices of a graph G, let Tbe an Steiner tree for S. We call vertices of S terminals and vertices of T−Sof degree ≥3 in T Steiner points. We will say that a Steiner point sis adjacent in Tto a terminal tif the path connecting sand tin Tdoes not contain other Steiner points. We call peripheral those Steiner points adjacent to at least two terminals. Theorem 5. For any set of vertices S of a connected HHD-free graph G, any Steiner tree T of S is contained in the geodesical convex hull of S. Proof. We will prove the assertion by induction on the cardinality of S, starting from the obvious case |S| = 2. Let Tbe a Steiner tree of S, with |S| = k≥3. Firstly, we may assume that all terminals are placed on leaves of T. If some terminal t∈Sis an inner vertex of T, then Tcan be viewed as the union of subtrees T1,...,Tmhaving tas a leaf. They are Steiner trees for sets of terminals S1, . . . Smlocated in these subtrees (notice that Ti∩Tj=Si∩Sj= {t}, for all 1 ≤i<j≤m and S1∪ · · · ∪ Sm=S). Our induction hypothesis gives Ti⊆CHg(Si), i=1,...,m. Since CHg(Si)⊆CHg(S), we obtain the desired inclusion V(T)⊆CHg(S). Let Tbe a Steiner tree of Swhere all terminals are leaves, so |S| ≥ 3 assures us that Thas at least one peripheral Steiner point s, adjacent to terminals t,t0. Firstly suppose that a peripheral point ssatisfies s∈CHg(S), and let Pbe the path on T between tand t0. The minimality of Tgives that Pis the union of a shortest path Ptbetween t and s, and a shortest path Pt0between t0and s, so in this case V(P)⊆CHg(S). Let T0be the tree obtained from Tremoving the path P, but keeping vertex s. Then T0is an Steiner tree for the set S0=(S\ {t,t0})∪ {s}, because if T0 0is a smaller tree, then adjoining to T0 0the path Pwe obtain a connected subgraph spanning S, but having less vertices than T, contradicting the optimality of T. Hence T0is minimal, and the inductive hypothesis gives V(T0)⊆CHg(S0). So, if s∈CHg(S)we are done, because in this case V(T0)⊆CHg(S0)⊆ CHg(S)and P⊆CHg(S), thus V(T)=V(T0)∪V(P)⊆CHg(S). Now we suppose that all peripheral Steiner points of Tare located outside CHg(S), and let sbe such a point, adjacent to two terminals tand t0. Then the path Pon Tbetween tand t0is not a shortest path on G, because it contains s, but subpaths Ptand Pt0between sand tand t0 730 J. C´ aceres et al. / European Journal of Combinatorics 29 (2008) 726–736 respectively are shortest paths by minimality of T. Let u1be the neighbor of sin Pt, let v1be the neighbor of sin Pt0and let Qbe a shortest path in Gbetween tand t0. Note that in case u1=t, the tree obtained from Tremoving subpath Pt0but keeping vertex sand adding path Q, or has smaller size than T(if |Q|<|P| − 1= |Pt0|) which is not possible, or it has the same size as T(if |Q| = |P| − 1= |Pt0|) and it is a Steiner tree of Swith a terminal t=u1which is not a leaf, so s∈CHg(S), a contradiction with our hypothesis. Thus we may assume that u16= t, and using a similar argument, v16= t0. Using that Gis a HHD-free graph, we obtain that peripheral vertex sis a neighbor of a vertex qin Q\ {t,t0}or u1and v1are adjacent in G(see Appendix). Let us see that the peripheral vertex s, adjacent to two terminals tand t0, cannot be a neighbor of any vertex q(q6= t,t0) lying in a shortest path Qbetween both terminals. Suppose to the contrary that it can and call S∗=(S\ {t,t0})∪ {q}, so |S∗|<|S|and the inductive hypothesis gives that any Steiner tree T∗of S∗satisfies V(T∗)⊆CHg(S∗)⊆CHg(S). We build a new tree T◦removing from Tpath P, but keeping vertex sand adding edge sq. It is clear that T◦contains vertex s, so V(T◦)6⊆ CHg(S), but on the other hand it spans S∗, so T◦is not a Steiner tree of S∗. Thus |T∗|<|T◦|=|T0|+ 1 (remember that T0is the tree obtained from Tremoving path P but keeping vertex s). So |T∗|≤|T0|and |T∗| + |Q|<|T0| + |P|=|T|(note that |Q|<|P|). Finally, the size of the tree spanned by V(T∗)∪V(Q), that covers S, is smaller than the size of T, which is a contradiction with the optimality of T. Let us see now that vertices u1and v1cannot be neighbors in G, which is a contradiction with the hypothesis “all peripheral Steiner points of Tare located outside CHg(S)”, which concludes induction. Suppose that u1and v1are neighbors, and call T1the Steiner tree of Sobtained from Tby removing edge sv1and adding edge u1v1. Note that vertex sets of Tand T1agree and u1 becomes a peripheral Steiner point of T1adjacent to tand t0. If u1∈CHg(S), using a preceding argument, V(T)=V(T1)⊆CHg(S), which is a contradiction with the hypothesis s6∈ CHg(S). So u16∈ CHg(S)and T1is a Steiner tree on the same conditions than T. So if u2is the neighbor of u1in the path to t, again u2and v1are neighbors in G(because if u1is a neighbor of a vertex qin a shortest path between tand t0, using a preceding argument, we obtain a tree smaller than T1, so than T, spanning S, which is not possible). But if u2and v1are neighbors in G, the tree obtained from Tremoving vertex u1and edges su1,u1u2and adding edge v1u2, spans Sand it has smaller size than T, which is not possible.  Theorem 6. Let G be a connected HHD-free graph and let S ⊆V(G). Then S is a g-convex set if and only if it is a St-convex set. Proof. The inclusion CHg(S)⊆CHSt(S)in Proposition 3 gives the sufficiency. Conversely, suppose that Sis a g-convex set and let Ta Steiner tree in Gof A⊆S; then V(T)⊆CHg(A)⊆ CHg(S)=S, so Sis St-convex.  4. St-convexity as a convex geometry A convexity is said to be a convex geometry (see [15]) if every convex set is the convex hull of its extreme points. This property gives good behavior to a convexity in graphs, because in this case we can keep all information about a convex vertex sets just in its extreme points. To find conditions under which St-convexity shares this property, we firstly need to characterize extreme points of a St-convex set. Recall that a vertex is called simplicial if its neighborhood is a complete subgraph. The next lemma shows that St-extreme points are simplicial vertices, the same condition as in case of g-convex sets. J. C´ aceres et al. / European Journal of Combinatorics 29 (2008) 726–736 731 Fig. 2. 3-fan. Lemma 7. Let S be a St-convex vertex set of a connected graph G, then St-extreme points of S are the simplicial vertices in the subgraph induced by S. Proof. If p∈Sis a St-extreme point, then S\ {p}is St-convex and so it is g-convex. Thus if p is a g-extreme point of S, it is simplicial (see [7]). Reciprocally, let p∈Sbe a simplicial vertex, and A⊆S\ {p}. Suppose that pis in a Steiner tree Tof A. Using that pis simplicial in S, build a new tree T0, removing from Tedges which are incident to pand adding edges from one of the neighbors of pto all the other ones, and them to p. It is clear that T0has the same vertex set as T, and pis an endvertex of T0. Finally the tree that results by removing pfrom T0contains Aand it is smaller than T, which is not possible because Tis a Steiner tree of A. So pis not in any Steiner tree of A⊆S\ {p}, which means that S\ {p}is a St-convex set and pis an St-extreme point of S. Note that, in any case, the extreme points of the convex hull of a set of vertices Abelong to A, because if p∈CH(A)\Ais an extreme point; then CH(A)\ {p}is a convex set containing A, which contradicts the minimality of convex hull. Now we can characterize the class of graphs in which St-convexity becomes a convex geometry. Theorem 8. The St-convexity in a connected graph G is a convex geometry if and only if G is chordal and contains no induced 3-fan. Proof. For the sufficiency, note that a chordal graph with no induced 3-fan is distance-hereditary, so St-convexity coincides with g-convexity, which is a convex geometry (see [7]). For the necessity, let Gbe a graph such that any St-convex vertex-set is the St-convex hull of its extreme points. Let us first see that Ghas no induced 3-fan. Suppose on the contrary, that F= {a,b,c,d, v}(see Fig. 2) is the vertex set of an induced 3-fan in G. We consider two cases. 1. If Fis St-convex, then extreme points of Fare aand d, whose St-convex hull does not contain bnor c, in contradiction with the hypothesis. 2. If Fis not St-convex, then the extreme points of CHSt(F)belong to {a,d}. If any of aor d are not extreme points, the contradiction with the hypothesis is clear. So suppose that both of them are the extreme points of CHSt(F). Then CHSt({a,d})consists of a,dand their common neighbors, and hence contains neither bnor c. Finally we show that Gis chordal using the well-known following characterization of chordal graphs: every induced subgraph has a simplicial vertex. So let G0be an induced subgraph of G and A=V(G0). There are two cases. 1. If Ais a St-convex set, by hypothesis, Ais the St-convex hull of its extreme points, so Ahas some extreme points, which are simplicial vertices of G0. 2. If Ais not St-convex, then let S=CHSt(A)be. Again Sis the St-convex hull of its extreme points, which are simplicial vertices of the subgraph induced by S. Let pbe one of these extreme points; then p∈Aand so pis a simplicial vertex of G0. 732 J. C´ aceres et al. / European Journal of Combinatorics 29 (2008) 726–736 In order to generalize this property, we look for a vertex set, other than St-extreme points, that allows us to rebuild a St-convex set by means of St-convex hull operation further than chordal graphs without an induced 3-fan. In view of Theorem 8, this new vertex set must be bigger than the St-extreme vertices, and in order to obtain it, we will follow the ideas in [2], where contour vertices of a graph Gare defined. Remember that, if vis a vertex of a connected graph G, the eccentricity e(v) of vis defined by e(v) =max{d(u, v):u∈V(G)}. A vertex vis called a contour vertex if e(v) ≥e(u), ∀u∈N[v](see [2]). We now use the n-eccentricity of a vertex, as defined in [3], to translate this concept to Steiner distance. Until the end of the paper, Gwill be a connected graph of order p≥2 and nwill be an integer with 2 ≤n≤p. Let S⊆V(G)and v∈S, the n-eccentricity en,S(v) de ven Sis defined by en,S(v) =max{dS(K):K⊆S,|K| = n, v ∈K}. In case S=V(G), we denote en,Ssimply by en. This concept is defined in [3], and it is used to obtain graph invariants similar to radius and diameter, and plays the role of eccentricity because it shares many of its properties. One of them, as can be seen in the next result, is that n-eccentricities of neighbors differ, at most, by one unit. Proposition 9. Let G be a connected graph and let uvbe an edge of G, then en(u)−1≤ en(v) ≤en(u)+1. Proof. Suppose on the contrary that en(u)+2≤en(v) and let R⊆V(G)such that |R| = n, v ∈R,en(v) =d(R). We define R0=Rif u∈R, or R0=(R\ {v})∪ {u}if u6∈ R. Thus |R0| = nand u∈R0. Let T0be a Steiner tree of R0; then |T0| = d(R0)≤en(u). Let us call Tthe tree obtained from T0adding edge uv, then Tspans Rand satisfies the inequality |T|≤|T0| + 1≤en(u)+1<en(u)+2≤en(v) =d(R), which is not possible by the definition of d(R). So en(v) ≤en(u)+1, and analogously en(u)≤en(v) +1, as desired.  Our main interest about n-eccentricity is that it will allow us to translate the definition of contour vertices to the environment of Steiner distance. Definition 10. Let Gbe a connected graph and S⊆V(G). A vertex v∈Sis called n-contour of Sif it satisfies en,S(v) ≥en,S(u), ∀u∈NS[v]. The set Ctn,S(G)of n-contour vertices of Sis called the n-contour set of S. The first property we can observe in the n-contour set is that it is an enlargement of St-extreme point set. Proposition 11. Let G be a connected graph and S ⊆V(G). Then Ctn,S(G)contains all Stextreme points of S. Proof. Let vbe an St-extreme point of S; this means NS[v]induces a complete subgraph; let u∈NS[v]. We will see that en,S(v) ≥en,S(u). Let R⊆Ssuch that |R| = n,u∈R,en,S(u)= dS(R). We consider two different cases. Firstly, if v∈R, it is clear that en,S(v) ≥dS(R)=en,S(u), as desired. So suppose now that v6∈ R. Then we build R0=(R\ {u})∪ {v}, and let T0be a Steiner tree of R0in S. If u∈V(T0), then T0spans R, and so en,S(u)=dS(R)≤ |T0| = dS(R0)≤en,S(v), as desired. On the contrary, if u6∈ V(T0), let wbe a neighbor of vin T0and we build a tree T, from T0, as follow: remove edges xv, ∀xneighbor of vin T0, remove vertex vand add vertex u. Using the fact that vis an St-extreme point of S, neighbors of vin Sare also neighbors of w, so add edges xw, ∀xneighbor of vin T0, and edge uw. J. C´ aceres et al. / European Journal of Combinatorics 29 (2008) 726–736 733 It is clear that resulting subgraph Tis a tree in S, with the same size than T0and spans R, so en,S(u)=dS(R)≤ |T|=|T0| = dS(R0)≤en,S(v), which concludes proof.  Now we prove the main result for n-contour vertices: these vertices can rebuild any Stconvex set by means of a Steiner convex hull operation. This result provides, in some sense, a generalization of Theorem 8, using a vertex set bigger than St-extreme points, that works in any connected graph. Theorem 12. Let G be a connected graph and S ⊆V(G)a St-convex set. Then CHSt(Ctn,S(S)) =S. Proof. Note that Ctn,S(S)⊆S,SSt-convex, implies CHSt(Ctn,S(S)) ⊆S. To complete the proof, suppose on the contrary that S\CHSt(Ctn,S(S)) 6= ∅ and let u∈S\CHSt(Ctn,S(S)) such that en,S(u)≥en,S(v), ∀v∈S\CHSt(Ctn,S(S)). Then u6∈ Ctn,S(S) and there exists v∈NS[u]such that en,S(v) > en,S(u), so v∈CHSt(Ctn,S(S)), by definition of u. Let R⊆Ssuch that |R| = n, v ∈R,en,S(v) =dS(R). We will see that R⊆CHSt(Ctn,S(S)). Let x∈R, by definition of n-eccentricity, it is true that en,S(x)≥d(R)=en,S(v) > en,S(u), and so x∈CHSt(Ctn,S(S)), as desired. In particular u6∈ R, and we define R0=(R\ {v})∪ {u}. It is clear that R0⊆S,|R0| = n,u∈R0, and thus dS(R0)≤en,S(u) < en,S(v) =dS(R). Then dS(R0)+1≤dS(R). Let T0be an Steiner tree of R0in S, and we build a new tree Tadding T0edge uv. Then Tis a tree in Sthat spans Rand it satisfies the inequality |T|≤|T0| + 1=dS(R0)+1≤dS(R). So Tis a Steiner tree of Rin Sthat contains u. Now, using that R⊆CHSt(Ctn,S(S)), vertices in any Steiner tree of Rbelong to CHSt(Ctn,S(S)), and so u∈CHSt(Ctn,S(S)), which is a contradiction with the election of u. Finally S\CHSt(Ctn,S(S)) = ∅, and we are done.  Acknowledgments Authors would like to thank the anonymous referees for their valued suggestions about the point of view of the paper and the proof of Theorem 5. The first and third authors were partially supported by BFM2001-2474 and FQM-305 grants, and the second author was partially supported by BFM2001-2474 and FQM-164 grants. Appendix Using that Gis a HHD-free graph, let us see that peripheral vertex sis a neighbor of a vertex qin Q\ {t,t0}or u1and v1are adjacent in G. Note that, using the minimality of tree T, vertex v1cannot be a neighbor of any vertex in Ptother than sand (perhaps) u1. In the same way, u1 cannot be a neighbor of any vertex in Pt0other than sand (perhaps) v1. We denote by zthe vertex in V(Pt)∩V(Q)further from t(maybe z=t), and we denote by z0the vertex in V(Pt0)∩V(Q) further from t0(maybe z0=t0). Consider the cycle Cconsisting of the subpath of Ptfrom sto z, the subpath of Qfrom zto z0and the subpath of Pt0from z0to s. Case 1: Cis a 3-cycle, so it is (z=u1)s(v1=z0), and u1, v1are adjacent in G. Note that if Cis a n-cycle, with n≥4, we cannot have both u1=zand v1=z0, because Q is a shortest path with |Q|<|P|, so dQ(z,z0) < dP(z,z0). Thus, in the case where u1=zand v1=z0, we obtain dP(z,z0)=2 and dQ(z,z0)=1, and Cis a 3-cycle. In the following cases we may assume, without loss of generality, that z06= v1. 734 J. C´ aceres et al. / European Journal of Combinatorics 29 (2008) 726–736 Fig. 3. Cis a 5-cycle. Path Qin dotted line. Fig. 4. The cycle C0in case Cis a k-cycle, k≥6. Case 2: Cis a 4-cycle, so it is (z=u1)sv1z0. Then u1is a neighbor of vertex z0, lying in Pt0, different from sand v1, which is not possible. So Ccannot be a 4-cycle. Case 3: Cis a 5-cycle. Then Cis (z=u1)sv1yz0, with ya vertex in Pt0, neighbor v1and z0, or (z=u1)sv1z0w, with wa vertex in Qneighbor of zand z0, or zu1sv1z0. In the first case (see Fig. 3(a)) u1is a neighbor of z0, lying in Pt0, different from sand v1, which is not possible. In second case (see Fig. 3(b)), using that Gis hole-free, the 5-cycle must have a chord which cannot be sz0by the minimality of Pt0, nor u1z0by the minimality of Q, so it must be that u1v1, and u1, v1are neighbors in G, or swand sis a neighbor of a vertex in Qother than t,t0, or v1w, and we obtain a house, which cannot be induced, so u1v1or swmust be edges (no other one is suitable). In the last case (see Fig. 3(c)), the 5-cycle must have a chord, which cannot be v1z, u1z0,sz or sz0(by similar arguments that above), so it must be that u1v1and u1,v1are adjacent in G. Case 4: Cis a k-cycle with k≥6. Suppose, on the contrary, that neither sis a neighbor of any vertex in Q\ {t,t0}, and nor are u1and v1adjacent in G. Using that Gis hole-free, edge u1smust be contained in a triangle or in a 4-cycle in C(see Lemma 2.2 in [5]). Under our hypothesis, a triangle is not possible, because shas no neighbors in Cother than u1,v1and they are not neighbors, and there is just one suitable 4-cycle: u1and v1have a common neighbor q in the subpath of Qbetween zand z0, so the 4-cycle is qu1sv1(see Fig. 4). We pick vertex the qas close as possible to z0. Note that q6= z0, because qis a neighbor of u1and u1cannot be a neighbor of z0, which lies on Pt0and it is not sor v1. So edge qv1, the subpath of Pt0from v1to z0and the subpath of Qfrom z0to q, make a cycle C0(with length at least 3) (see Fig. 4). Using again that Gis hole-free, edge v1qmust be contained in a triangle or in a 4-cycle with vertices in C0. Firstly suppose that edge v1qis contained in a triangle with vertices in C0. If the third vertex in the triangle is on Q, it must be q0the neighbor of qin C0other than v1, by minimality of Q(see Fig. 5(a)). On the other hand, if the third vertex is on Pt0it must be v0 1the neighbor of v1in C0other than q, by minimality of Pt0(see Fig. 5(b)). In both cases following conditions gives an induced house, which is not possible in G:u1is no neighbor of v1by hypothesis, it is no neighbor of q0, which is a neighbor of v1closer to z0than q, and it is no neighbor of v0 1by minimality of T, on the other hand vertex sis no neighbor of qnor q0by hypothesis and it is no neighbor of v0 1by minimality of Pt0. So edge v1qis not contained in any triangle in C0. Therefore edge v1qmust be contained in a 4-cycle in C0. The other two vertices in the four cycle can be both in Pt0, both in Qor one in Pt0and the other one in Q. If both are in Pt0, the 4-cycle is qv1v0 1v00 1with v00 1as the neighbor of v0 1in C0other than v1(see Fig. 6(a)). If they are both in Q, the 4-cycle is v1qq0q00 with q00 as the neighbor of q0in C0other than q(see Fig. 6(b)).