On the mixed connectivity conjecture of Beineke and Harary

Johann, Sebastian S.; Krumke, Sven O.; Streicher, Manuel Article — Published Version On the mixed connectivity conjecture of Beineke and Harary Annals of Operations Research Provided in Cooperation with: Springer Nature Suggested Citation: Johann, Sebastian S.; Krumke, Sven O.; Streicher, Manuel (2023) : On the mixed connectivity conjecture of Beineke and Harary, Annals of Operations Research, ISSN 1572-9338, Springer US, New York, NY, Vol. 332, Iss. 1, pp. 107-124, https://doi.org/10.1007/s10479-023-05527-8 This Version is available at: https://hdl.handle.net/10419/317733 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/4.0/ Annals of Operations Research (2024) 332:107–124 https://doi.org/10.1007/s10479-023-05527-8 ORIGINAL RESEARCH On the mixed connectivity conjecture of Beineke and Harary Sebastian S. Johann1 ·Sven O. Krumke1 ·Manuel Streicher1 Received: 20 December 2021 / Accepted: 7 July 2023 / Published online: 15 August 2023 © The Author(s) 2023 Abstract The conjecture of Beineke and Harary states that for any two vertices which can be separated by kvertices and ledges for l≥1 but neither by kvertices and l−1 edges nor k−1 vertices and ledges there are k+ledge-disjoint paths connecting these two vertices of which k+1 are internally disjoint.In this paper we prove this conjecture for l=2andeveryk∈N.We utilize this result to prove that the conjecture holds for all graphs of treewidth at most 3 and all kand l. Keywords Mixed connectivity ·Mixed cut ·Menger ·Graph theory Mathematics Subject Classification 05C40 ·05C38 1 Introduction Connectivity is an extensively studied property of graphs. A well-known Theorem of Menger establishes equality between the vertex connectivity for a given pair of non-adjacent vertices and the maximum number of internally disjoint paths between this pair as well as the edge connectivity for a given pair of vertices and the maximum number of edge-disjoint paths betweenthispair.TherearemanyvariationandextensionsofMenger’sTheorem.Forexample Aharoni and Berger (2008) proved a version of Menger’s Theorem for infinite graphs and Borndörfer and Karbstein (2012) interpreted and proved Menger’s Theorem in hypergraphs. In this paper we focus on a form of connectivity in which vertices and edges may be removed at the same time. One variant of mixed connectivity was considered by Egawa et al. (1991). They prove the following mixed version of Menger’s Theorem: Between two vertices v, w of a graph there are λedge-disjoint unions of kinternally disjoint paths if and only if for each set Sof 0 ≤r≤min{k−1,|V(G)|−2}vertices the graph G−Scontains λ(k−r) edge-disjoint v-wpaths. BSven O. Krumke sven.krumk[email protected] Sebastian S. Johann [email protected] Manuel Streicher [email protected] 1Department of Mathematics, University of Kaiserslautern-Landau, Kaiserslautern, Germany 123 108 Annals of Operations Research (2024) 332:107–124 Beineke and Harary (1967) proposed an alternative form of mixed connectivity between pairs of vertices. They call a pair of non-negative integers (k,l)connectivity pair for distinct vertices sand tif they can be separated by removing kvertices and ledges, but neither by k vertices and l−1 edges nor k−1 vertices and ledges. In the same publication Beineke and Harary claim to have proved a mixed version of Menger’s Theorem: If (k,l)is a connectivity pair for sand t, then there exist k+ledge-disjoint s-tpaths kof which are internally disjoint. Mader (1979) pointed out that the proof is erroneous. More recently, mixed connectivity has been revisited by Erves and Zerovnik (2016), who regard transferrance of mixed connectivity along cartesian graph products and bundles, and Bonnet and Cabello (2021) who regard the parametrized complexity of mixed connectivity. The main focus of this paper, however, is the conjecture by Beineke and Harary. The most meaningful result on the conjecture to date is due to Enomoto and Kaneko (1994). They first extended the conjecture claiming that it is possible to find k+1 internally disjoint paths instead of just kunder the additional assumption that l≥1 and then proved their statement for certain kand l. The exact result is restated as Theorem 5in Sect.2. From our studies the following conjecture originally formulated by Beineke and Harary and extended by Enomoto and Kaneko may hold. In the remainder of this article we refer to the conjecture by the name Beineke-Harary-Conjecture. Conjecture (Beineke-Harary-Conjecture) Let G be a graph, s,t∈V(G)distinct vertices and k,l non-negative integers with l ≥1.If(k,l)is a connectivity pair for s and t in G, then there exist k +l edge-disjoint paths, of which k +1are internally disjoint. Our main contribution is to prove the conjecture for l=2andanyk∈N.Itisworth noting that forl=2 the conjecture has not been proved for any k>1. In particular, the result of Enomoto and Kaneko does not apply to these cases and their proof does not appear to have an easy adaption for these cases. The techniques used to prove the conjecture for l=2 are novel. The main idea is to start with kinternally disjoint paths and then find the missing path by inductively moving through the graph and adjusting the kinternally disjoint paths whenever necessary. We observe that our result, together with the result due to Enomoto and Kaneko, cf. Theorem 5, implies that the Beineke-Harary-Conjecture holds for k=2andall l∈N. We then utilize this fact to prove the Beineke-Harary-Conjecture for all graphs that have treewidth at most 3. Outline. After we state some basic definitions in Sect.2, we establish some preliminary results on connectivity pairs and the Beineke-Harary-Conjecture in Sect.3.Wepresentthe proof of our main result in the subsequent Sect.4. Section5focuses on proving the conjecture on graphs of small treewidth. The results of this article are also published in the PhD theses of Johann (2021)and Streicher (2021). 2 Preliminaries Most of our notation is standard graph terminology as can be found in West (2001). We recall some basic notations in the following. The graphs under consideration may contain parallels but no loops. For a graph G, we refer to the vertex set of the graph Gby V(G)and to the edge set by E(G). We denote an edge joining vertices u,v ∈V(G)by uv. Note that the exact choice of the edge, if parallel edges are present, is not of relevance to any of our proofs. For U,V⊆V(G)and u∈Uand v∈Vwe call uvaU-Vedge. The set of all 123 Annals of Operations Research (2024) 332:107–124 109 U-Vedges in E(G)is denoted by E(U,V); instead of E({u},V)and E(U,{v})we write E(u,V)and E(U,v).IfHis another graph we denote by G∪Hthe graph with vertex set V(G)∪V(H)and edge set E(G)∪E(H), where we assume that equal edges join the same set of endvertices. For a subset of vertices S⊆V(G)we denote by G[S]the graph induced by S,thathasvertexsetSand all edges joining vertices of S. Further, we denote by G−S the graph G[V(G)\S]. For a subset E⊆Ewe write G−Efor the graph with vertex set V(G)and edge set E\E. To simplify notation we write G−vand G−einstead of G−{v} and G−{e}for v∈V(G)and e∈E(G). Apath P =v0...v kis a graph with vertex set {v0,...,v k}and associated edge set {vivi+1:i=0,...,k−1},whereallverticesaredistinctexceptpossiblyv0andvk.Ifv0= vk we refer to Pas a v0-vkpath.WedenotebyviPvjwith i≤jthe subpath vivi+1...vj. If vi=v0(vj=vk) for simplicity of notation we also write Pvj(viP). Two or more paths are edge-disjoint if no two paths use the same edge. Two or more s-tpaths are internally disjoint if they only share the vertices sand t.IfP1,...,Pkare internally disjoint s-tpaths, we call the graph k i=1Pian s-t k-skein. For distinct vertices sand twe say that a set W⊆V(G)\{s,t}(F⊆E(G))separates sand tin Gif sand tare not connected in G−W(G−F). In this case we call W(F) an s-t vertex-(edge-)separator.Ifsand tare non-adjacent, we denote by κG(s,t)the size of a smallest vertex-separator for sand t, where we omit the subscript Gif the graph is clear from context. For a graph GasetWis a vertex-separator if G−Wis not connected. 3 Connectivity pairs and foundations of the Beineke–Harary-conjecture Inthis section weprovidetheformaldefinition for connectivitypairs,recall some basicresults on the Beineke–Harary-Conjecture, and establish further basic results on mixed separators and the conjecture. Definition 1 (Disconnecting pair) Let Gbe a graph and S,T⊆V(G). We call a pair (W,F) with W⊆V(G)\(S∪T)and F⊆E(G)an S-T disconnecting pair if in G−W−Fthere is no path from a vertex in Sto a vertex in T. We call the number of edges in a disconnecting pair its size, the number of vertices in a disconnecting pair its order and the number of elements |W|+|F|to be its cardinality. If S={s}or T={t}consists of only one element we omit the set brackets in the notation and also write s-tdisconnecting pair. Beineke and Harary (1967) introduced connectivity pairs. We recall their definition in the following. Definition 2 (Connectivity Pairs) Let Gbe a graph and s,t∈V(G)distinct vertices. We call an ordered pair of non-negative integers (k,l)aconnectivity pair for sand tin Gif (i) there exists an s-tdisconnecting pair of order kand size land (ii) there is no s-tdisconnecting pair of cardinality less than k+lhaving order at most kand size at most l. As Property (ii) implies, that there exist kvertices other than sand tand at least ledges, we may replace Property (ii) by (ii)’ there is no s-tdisconnecting pair of order kand size l−1ororderk−1andsizel. 123 110 Annals of Operations Research (2024) 332:107–124 Further, if there are fewer than ledges between sand t, then we can replace Property (ii) by (ii)” there is no s-tdisconnecting pair of order kand size l−1 This is true since we may replace any edge in an s-tdisconnecting pair by a vertex incident to it unless the edge joins sand t. The Beineke-Harary-Conjecture is, in some sense, a mixed version of Menger’s Theorem. As we make use of it, we recall three versions of Menger’s Theorem here. Theorem 1 (Menger’s Theorem) Let s and t be two distinct vertices of a graph G. (i) If st /∈E(G), then the minimum number of vertices separating s and t in G is equal to the maximum number of internally disjoint s-t paths. (ii) The minimum number of edges separating s and t in G is equal to the maximum number of edge-disjoint s-t paths in G. (iii) The minimum cardinality of an s-t disconnecting pair is equal to the maximum number of internally disjoint s-t paths. Proof Proofs for the statements (i) and (ii) can be found, for example, in West (2001). The statement (iii) is a direct consequence of (i): Any edge joining sand tinduces an s-tpath that is internally disjoint to all other s-tpaths. Also every edge joining sand tis contained in every s-tdisconnecting pair. The statement now follows considering that any edge in an s-t disconnecting pair that does not join sand tcan be replaced by one of its endvertices.  Menger’s Theorem implies the Beineke-Harary-Conjecture for a couple of base cases regarding the integers kand l. Observation 2 Let k ≥0and l ≥1be integers and let s and t be two distinct vertices of a graph G. (i) If (k,0)is a connectivity pair for s and t, then s and t are not adjacent. Further, the minimum number of vertices separating s and t is k and, by Menger’s Theorem, there exist k internally disjoint s-t paths. (ii) If (k,1)is a connectivity pair for s and t, then s and t are k +1vertex-connected in G and hence, by Menger’s Theorem, there are k +1internally disjoint paths between s and t. (iii) If (0,l)is a connectivity pair for s and t, then s and t are l edge-connected in G and hence, by Menger’s Theorem, there are l edge-disjoint paths between s and t. Another rather basic result implies that it suffices to prove the Beineke-Harary-Conjecture for non-adjacent vertices as we see in the following two lemmas. Lemma 3 Let G be a graph, s,t∈V(G)be two distinct vertices and let k,l be non-negative integers. The pair (k,l)is a connectivity pair for s and t in G if and only if (k,l−|E(s,t)|) is a connectivity pair for s and t in G −E(s,t). Proof Any s-tdisconnecting pair in Ghas to contain all edges in E(s,t). Thus, we get a oneto-one correspondence between the s-tdisconnecting pairs in Gand the ones in G−E(s,t) bymapping apair(W,F)to thepair (W,F\E(s,t)).Thedesired resultfollows immediately.  123 Annals of Operations Research (2024) 332:107–124 111 Lemma 4 Let Gbe a class of graphs which is closed under deletion of edges. If the BeinekeHarary-Conjecture holds for all graphs G ∈Gand all vertices s,t∈V(G)such that s and t are not adjacent, then the conjecture holds for all graphs G ∈Gand all vertices s,t∈V(G). Proof Assume the Beineke-Harary-Conjecture holds for all graphs G∈Gand all vertices s,t∈V(G)with |E(s,t)|=0. Let G∈Gbe a graph, s,t∈V(G)distinct vertices with |E(s,t)|≥1, and let (k,l)be a connectivity pair for sand tin G. By Lemma 3, (k,l−|E(s,t)|)is a connectivity pair for sand tin G−E(s,t). Thus, by assumption there exist k+l−|E(s,t)|edge-disjoint s-tpaths of which at least kare internally disjoint in G−E(s,t). Note that we cannot assume that k+1 paths are internally disjoint, as l−|E(s,t)|=0 is a possibility. Nevertheless, the k+l−|E(s,t)|paths together with the edges in E(s,t)yield k+ledge-disjoint s-tpaths of which at least k+1 are internally disjoint, as the edges in E(s,t)are internally disjoint to all s-tpaths and by assumption |E(s,t)|≥1.  Other than these simple observation the only meaningful result on the Beineke-HararyConjecture to date is due to Enomoto and Kaneko (1994). Their result implies the correctness for further base cases regarding the integers kand l. We mention one explicit choice as a corollary, as we make use of the statement later on. Theorem 5 (Enomoto and Kaneko (1994)) Let q, r, k and l be integers with k ≥0and l ≥1 such that k +l=q(k+1)+r, 1≤r≤k+1, and let s and t be distinct vertices of a graph G. If q +r>k and if (k,l)is a connectivity pair for s and t, then G contains k +l edge-disjoint s-t paths of which k +1are internally disjoint.  Corollary 6 Let (1,l)be a connectivity pair for two distinct vertices s and t of a graph G, then there are l +1edge-disjoint s-t paths of which two are internally disjoint. Proof For l=1 the statement holds due to Observation 2.Forl≥2andq,r∈Nwith 1+l= q·2+rand 1 ≤r≤2wehaveq+r>1 and by Theorem 5we get the desired paths.  Before we turn to the proof of the Beineke-Harary-Conjecture for l=2, we discuss an erroneous claim made by Sadeghi and Fan (2019). This serves to illustrate the difficulties when trying to prove Beineke-Harary-Conjecture and further shows why the conjecture does not claim equivalence of the existence of connectivity pairs and paths. The statement by Sadeghi and Fan is the following: When V (G)≥k+l+1, k≥0and l ≥1, a graph G has k +l edge-disjoint paths of which k +1are internally disjoint between any two vertices, if and only if the graph cannot be disconnected by removing k vertices and l −1edges. In Sadeghi and Fan (2019) for integers k,l≥1agraphGwith at least k+l+1 vertices is called (k,l)-connected if it cannot be disconnected by removing kvertices and l−1 edges. The following claim is then made. Let k,l≥1and Gbe a graph with at leastk+l+1 vertices. Then G is (k,l)−connected if and only if Gis k+1 vertex-connected and (1) k+ledge-connected. If Gis in fact (k,l)-connected it can readily be observed that it is also k+1 vertex-connected and k+ledge-connected. On the other hand Gbeing k+1 vertex-connected and k+ledgeconnected does not imply (k,l)-connectivity. To see this, consider the two complete graphs G1and G2on the vertex sets {x1,x2,x3,x4}and {x1,x5,x6,x7}. We construct a graph G 123 112 Annals of Operations Research (2024) 332:107–124 Fig. 1 A graph containing a vertex-edge separator, such that between any pair of vertices there exist three edge-disjoint paths of which two are internally disjoint by regarding the union of G1and G2and additionally adding an edge between vertices x5 and x2. Figure1displays the constructed graph. The graph Gis 2-vertex-connected and 3edge-connected, but it is not (1,2)-connected as the removal of the vertex x1and the edge x2x5disconnects the graph. Thus, the Claim (1) cannot hold. As a corollary of Claim (1), Sadeghi and Fan state the following. Let k≥0,l≥1,and Gbe a graph withat least k+l+1 vertices. Then Gis (k,l)−connected if and only if it hask+ledge-disjoint (2) paths between every pair of vertices of which k+1 paths are internally disjoint. Asa corollarytoClaim (1),Claim (2)cannot beconsidered proven. Wegiveacounterexample to the claim in Proposition 7. In the original conjecture by Beineke and Harary (1967) and in the extension due to Enomoto and Kaneko (1994) it is never claimed that the existence of the desired paths is sufficient for (k,l)-connectivity and, in fact, it is not. For the sake of completeness we argue why the existence of the paths in Claim (2) is not sufficient. Proposition 7 The graph G constructed above contains a separator of one vertex and one edge and between any pair of vertices there exist three edge-disjoint paths of which two are internally disjoint. Proof Consider the graph Gabove, that also provided a counterexample to Claim (1), see Fig.1.Thevertexx1together with the edge x5x2disconnects the graph. Now let v1,v 2∈V(G).Ifv1,v 2∈V(Gi)for some i∈{1,2}, then there are three internally disjoint v1-v2paths. Otherwise, without loss of generality v1∈{x2,x3,x4}and v2∈{x5,x6,x7}. Denote by P1a shortest path from v1to x2(This is either a single edge or the path without edges)and by P2ashortestpathfrom x5tov2.Wedefinethev1-v2path P:= (P1∪P2)+x2x5. Further, let Q=v1x1v2. Finally, let w1∈{x3,x4}\{v1}and w2∈{x6,x7}\{v2}and define the path R=v1w1x1w2v2. It is easily verified that P,Q,Rare three edge-disjoint v1-v2 paths and Pand Qare also internally disjoint.  The graph in Fig.1illustrates two things. On the one hand it shows that we may not hope to prove an equivalence in the fashion of Claim (2). On the other hand it shows that it is not possible to replace the mixed form of connectivity by two separate statements on pure connectivity in the fashion of Claim (1). This is one of the reasons why the BeinekeHarary-Conjecture is not a consequence of Menger’s Theorem and its proof has not been established as of yet. It also suggests that the usual techniques used for proofs of Menger’s Theorem might not transfer to the mixed statement. In the following we use a novel technique 123 Annals of Operations Research (2024) 332:107–124 113 for proving the Beineke-Harary-Conjecture for the case that l=2. The idea is to keep the desired k+1 internally disjoint paths and move from sto talong the remaining path. The statement is then proved by induction. 4 The Beineke–Harary-Conjecture for disconnecting pairs of size 2 Now that we have established some foundations for connectivity pairs and the BeinekeHarary-Conjecture, we turn to the main result of this contribution. We prove that the Beineke– Harary-Conjecture holds for all non-negative integers kif l=2. Theorem 8 Let G be a graph and s,t∈V(G). Further, let (k,2)be a connectivity pair for s and t. Then, there exist k +2edge-disjoint s-t paths of which k +1are internally disjoint. Before we begin with the proof, note that the result of Theorem 8has only been proved for k=1. In particular, the result of Enomoto and Kaneko, cf. Theorem 5, basically tackles the conjecture from a different angle: In their statement for k≥2andl=2, the sum q+r always equals 2, which leads to a large gap between kand q+rfor large k. The idea of the proof of Theorem 8for vertices s1and tis to always keep an s1-t(k+1)- skein and inductively move along some other s1-tpath Pwhich is edge-disjoint to the currently regarded s-t(k+1)-skein. In order to use induction we generalize the claim of Theorem 8. Theorem 9 Let G be a graph, s1,s2,t∈V(G)with s1= t. Further, assume that (i) there exists an s2-t path in G, (ii) there exists an s1-t (k+1)-skein in G, and (iii) there is no {s1,s2}-t disconnecting pair of cardinality k +1and order at most k in G. Then, there exist k +2edge-disjoint paths, of which k +1are internally disjoint s1-t paths and one is an s2-t path. Proof Let Gbe a graph, s1,s2,t∈V(G)with s1= tsatisfying Properties (i) to (iii).We prove the claim by induction on the number of edges |E(G)|.If|E(G)|≤k, then there cannot be k+1 internally disjoint s1-tpaths, as s1= t. The base case of the induction is thereby represented by all graphs with at most kedges. Thus, from now on we may assume the following. LetGbea graph with |E(G)|<|E(G)|and vertices s 1,s 2,t∈V(G)with s 1= t.If Properties(i)to(iii)aresatisf ied in G,thenthereexist k +2 edge −disjoint paths of which k +1areinternallydisjoint s 1−tpaths and of which one is an s 2−tpath. (3) We begin by proving the induction step for the case that s2is contained in an s1-t(k+1)-skein and afterwards use this result to prove the induction step for the case that s2is not contained in such a skein. Case 1: The vertex s2is contained in an s1-t(k+1)-skein. If s2=t, then the k+1 internally disjoint paths from Property (ii) together with the s2-t paths2=tform thedesired paths.Thus,we mayassume thats2= t.DenotebyP1,...,Pk+1 the s1-tpaths of an s1-t(k+1)-skein containing s2. Without loss of generality we may assume 123 114 Annals of Operations Research (2024) 332:107–124 Fig. 2 Case 1 in the proof of Theorem 9: Supposed separation of s1and t. The colored diamonds correspond to elements in (W,F). The dotted lines are mutually internally disjoint. The solid line is a single edge. The colored lines that are not solid indicate a connection of vertices that does not touch colored vertices or edges Fig. 3 Case 1 in the proof of Theorem 9: Supposed separation of {s1,s 2}and t. The colored diamonds correspond to elements in (W,F). The dotted lines are mutually internally disjoint. The solid line is a single edge. The colored lines indicate a connection of vertices that does not touch (W,F) s2∈V(Pk+1).Denotebys 2the vertex succeeding s2on Pk+1,i.e.Pk+1=s1...s2s 2...t, cf. Fig.4. Note that s1=s2is not forbidden at this point. We now want to use the induction hypothesis for G−s2s 2and the vertices s1,s 2and t,cf. Fig.2a). Property (i) is satisfied as s 2Pk+1is an s 2-tpath in G−s2s 2. Suppose that there do not exist k+1 internally disjoint s1-tpaths in G−s2s 2. By Menger’s Theorem there is an s1-tdisconnecting pair (W,F)of cardinality k. Since in G−s2s 2the internally disjoint paths P1,...,Pkstill exist, all elements of (W,F)are contained in the paths P1,...,Pk, cf. Fig.2a). Thus, the path Pk+1s2still exists in G−s2s 2−W−Fand (W,F)is an {s1,s2}-t disconnecting pair in G−s2s 2,cf. Fig.2b). By assumption (W,F∪{s2s 2})is not an {s1,s2}- tdisconnecting pair in Gand there exists some {s1,s2}-tpath in G−W−F−s2s 2,cf. Fig.2c), which yields a contradiction. Hence, Property (ii) is satisfied in G−s2s 2and s1,s 2,t. Now suppose there exists an {s1,s 2}-tdisconnecting pair (W,F)of cardinality k+1and order at most kin G−s2s 2. As the paths P1,...,Pk,s 2Pk+1are internally disjoint, each element of (W,F)is contained in one of these paths, cf. Fig.3a). Thus, Pk+1s2still exists in G−s2s 2−W−Fand neither s2nor s 2are contained in the same component as tin G−s2s 2−W−F. This implies that (W,F)is an {s1,s2}-tdisconnecting pair in G,cf. Fig.3b). Again this is a contradiction to Property (iii) in G,cf. Fig.3c) and hence Property (iii) is satisfied for G−s2s 2and s1,s 2,t. As G−s2s 2contains |E(G)|−1 edges, statement (3) is applicable and there exist k+2 edge-disjoint paths of which k+1 are internally disjoint s1-tpaths, say P 1,...,P k+1,and of which one is an s 2-tpath, say P k+2,cf. Fig.4b). If s2∈V(P k+2)the paths P 1,...,P k+1,s2P k+2are the desired paths in G. Otherwise the paths P 1,...,P k+1,s2s 2∪P k+2form the desired paths, cf. Fig.4c). Thus from now on, in addition to (3), we may assume: Let Gbe a graph with|E(G)|=|E(G)|and vertices s 1,s 2,t∈V(G)such that s 1= tands  2is contained in an s1−t(k+1)−skein.IfProperties(i) through (iii)aresatis f ied,thenthereexistk +2edge −disjointpathsof whichk +1areinternallydisjoints 1−tpathsandof whichoneisans 2−tpath. (4) 123 Annals of Operations Research (2024) 332:107–124 121 Fig. 8 Case 1 of the proof of Theorem 15:s-tpaths in H1and H2given by induction on the left. Creation of desired s-tpaths in Gon the right. Colored dotted lines indicate internally disjoint s-tpaths. Dashed line indicates an s-tpath that is edge-disjoint to all other indicated paths. Solid lines are single edges an s-apath in G1−W 1−F 1. Then, there is no a-tpath and (W 1∪W 2,F 1∪F 2)is an s-t disconnecting pair in Gof order kand size l2+l1−q<lby (5) — a contradiction. On the other hand if there does not exist ans-apath in G1−W 1−F 1, then the pair (W 1∪W,F 1∪F) is s-tdisconnecting in Gand of order kand size l−1, which again yields a contradiction.  Note that for i∈{1,2}it is V(Hi)=V(Gi)<V(G)and tw(Hi)≤3astw(Gi)≤3 and we only added edges between sand a, respectively aand tto get to Hifrom Gi.By Claim 2and the induction hypothesis there are k1+1+l1edge-disjoint s-tpaths in H1,say P1,...,Pk1+l1+1,ofwhichk1+2 are internally disjoint, cf. Fig.8. Without loss of generality let P1,...,Pr1be the paths using edges from {e1,...,eq}, where from these we denote by P1 thepath that isamongthe k1+2 internallydisjointpaths, if onesuchpath exists.Ifq=l2=0, then (k2,0)is a connectivity pair for sand tin G2−aby Claim 1, and by Observation 2 there are k2internally disjoint s-tpaths in G2−a. Together with P1,...,Pk1+l1+1we get the desired paths for G. So assume that q+l2>0. By Claim 3and the induction hypothesis there are k2+l2+qedge-disjoint s-tpaths in H2,sayQ1,...,Qk2+l2+qof which k2+1 are internally disjoint, cf. Fig.8. Without loss of generality let Q1,...,Qr2for r2≤qbe the paths using edges from {f1,..., fq}, where again from these we denote by Q1the path that is among the k2+1 internally disjoint paths, if one such path exists. We now claim that for r:= min{r1,r2}the paths Q1a∪aP 1,...,Qra∪aP r,Pr1+1,...,Pk1+l1+1,Qr2+1,...,Qk2+l2+q are at least k+ledge-disjoint s-tpaths of which at least k+1 are internally disjoint, cf. Fig.8. First note, that the number of paths is exactly r+(k1+l1+1)−r1+(k2+l2+q)−r2=k+l+q+r−r1−r2. As ris equal to rifor some iand qis greater than or equal to r1and r2we get that the number of paths is at least k+l. To see that among the paths above there are at least k+1 internally disjoint paths, note that we started off with a set of k1+2+k2+1=k+2 internally disjoint paths P⊆{P1,...,Pk1+l1+1,Q1,...,Qk2+l2+q}. The only vertex besides sand tthat may be contained in more than one path of Pis a.If Q1,P1∈Pthey are glued together and k+1 internally disjoint paths still remain. If only one of P1and Q1,sayP1, is among the internally disjoint paths, then P\{P1}is a set of k+1 internally disjoint paths, as only one other path than P1may contain a. Finally if neither P1 123 122 Annals of Operations Research (2024) 332:107–124 nor Q1are among the internally disjoint paths, then Pcontains a subset of internally disjoint paths of size k+1 as at most two paths in Pmay contain a. This concludes Case 1. Case 2: The vertex a is not contained in any s-t disconnecting pair of order k and size l. Denote by (W,F)an s-tdisconnecting pair of order kand size land for i∈{1,2}let Wi=V(Gi)∩W,ki=|Wi|,Fi=E(Gi)∩Ei,andli=|Fi|.Thenk1+k2=kand l1+l2=l. Without loss of generality we may assume that there is no s-apath in G−W−F and thereby also no s-apath in Gi−Wi−Fifor i∈{1,2}. For i∈{1,2}denote by 0 ≤qi≤lithe unique integer such that (ki,li−qi)is a connectivity pair for sand tin Gi. Note that this is well-defined as (Wi,Fi)is an s-t disconnectingpair in Gi.Wedefineq=max{q1,q2}andassumethatq=q1(thecaseq=q2 follows analogously). Let (W 1,F 1)be an s-tdisconnecting pair in G1of order k1and size l1−qand denote by H1the graph arising from G1by adding qedges e1,...,eqbetween a and t. Claim 4 (k1,l1)is a connectivity pair for s and t in H1. Proof If q=0, then the claim holds by definition of q. So assume that q≥1. Clearly (W 1,F 1∪{e1,...,eq})is an s-tdisconnecting pair in H1of order k1and size l1. So suppose there exits an s-tdisconnecting pair of order k1and size at most l1−1. Let (W,F)be such a pair of minimal size. If e1,...,eq∈Fthe pair (W,F\{e1,...,eq}) is s-tdisconnecting in G1and of order k1and size at most l1−q−1, contradicting the fact that (k1,l1−q)is a connectivity pair for sand tin G1.Thus,eithera∈Wor aand tare contained in the same component in H1−W−F. In particular, there is no s-apath in G1−W−Fand thereby the pair (W∪W2,F∪F2)is s-tdisconnecting in Gand of order kand size at most l−1. A contradiction to (k,l)being a connectivity pair for sand t in G. Let now H2be the graph arising from G2by adding qedges f1,..., fqbetween aand s. For H2we can also find a connectivity pair. Claim 5 (k2,l2+q)is a connectivity pair for H2. Proof Again, if q=0 the claim is immediate by definition of q.Soletq≥1.In this case we have that (W2,F2∪{f1,..., fq})is an s-tdisconnecting pair of order k2and size l2+q in H2. So suppose there exists an s-tdisconnecting pair of order k2and size at mostl2+q−1. Let (W,F)be such a pair of minimal size. If f1,..., fq∈F, then there is no s-apath in H2−W−F. This implies that (W∪W1,F\{f1,..., fq}∪F1)is a disconnecting pair in Gof order at most kand size at most l−1 yielding a contradiction. Thus, either a∈Wor aand sare contained in the same component in H2−W−F. In particular, there is no a-tpath in G2−W−F. If there is also no a-tpath in G1−W 1−F 1, the pair (W∪W 1,F∪F 1)is disconnecting in Gand of order at most kand size at most l−1. This yields a contradiction to (k,l)being a connectivity pair for sand tin G. So suppose that there is an a-tpath in G1−W 1−F 1. Then there is no s-apath in G1−W 1−F 1and (W 1∪W2,F 1∪F2)is an s-tdisconnecting pair in G, that has order at most kand size at most l1−q+l2<las q≥1. Again this contradicts the fact that (k,l)is a connectivity pair for sand tin G. As in the proof of Case 1 we use the induction hypothesis on H1and H2to get the desired paths. If neither l1=0 nor l2+q=0 we get the paths in Gin the same manner as in Case 1 and therefore do not repeat the arguments here. 123 Annals of Operations Research (2024) 332:107–124 123 For the other case, let l 1=l1and l 2=l2+q.Ifwecanshowfori∈{1,2},thatif l i=0, then in Gi−athe pair (ki,0)is a connectivity pair, we can again proceed as in Case 1 and get the desired paths. To see this we simply observe that ais not contained in any kivertex separator in Gias this would imply that ais contained in an s-tdisconnecting pair of order kand size lin G. 6 Conclusion and open problems In this article we considered a form of mixed connectivity in graphs introduced by Beineke and Harary, namely connectivity pairs. We prove the Beineke Harary Conjecture for the case that l=2. This result substantially differs from previous results in the literature and can be used to prove the conjecture on restricted graph classes. We illustrate the latter fact by proving the conjecture for graphs of treewidth at most 3. From our studies the BeinekeHarary-Conjecture may hold: Conjecture (Beineke-Harary-Conjecture) Let G be a graph, s,t∈V(G)distinct vertices and k,l non-negative integers with l ≥1.If(k,l)is a connectivity pair for s and t in G, then there exist k +l edge-disjoint paths, of which k +1are internally disjoint. Funding Open Access funding enabled and organized by Projekt DEAL. Declarations Conflict of interest The authors have no competing interests to declare that are relevant to the content of this article. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. References Aharoni, R., & Berger, E. (2008). Mengers theorem for infinite graphs. Inventiones Mathematicae, 176(1), 1–62. Beineke, L. W., & Harary, F. (1967). The connectivity function of a graph. Mathematika.https://doi.org/10. 1112/S0025579300003806 Bodlaender, H. L. (1998). A partial k-Arboretum of graphs with bounded treewidth. Theoretical Computer Science, 2091, 21–45. Bonnet, È., & Cabello, S. (2021). The complexity of mixed-connectivity. Annals of Operations Research, 30725, 35. Borndörfer, R., & Karbstein, M. (2012). A Note on Menger’s Theorem for Hypergraphs 12-03. BerlinZIB. Diestel, R. (2000). Graph Theory. Springer. Egawa, Y., Kaneko, A., & Matsumoto, M. (1991). A mixed version of Menger’s theorem. Combinatorica, 1171, 74. https://doi.org/10.1007/bf01375475 Enomoto, H., & Kaneko, A. (1994). The condition of Beineke and Harary on edge-disjoint paths some of which are openly disjoint. Tokyo Journal of Mathematics, 172355, 357. https://doi.org/10.3836/tjm/ 1270127958 123 124 Annals of Operations Research (2024) 332:107–124 Erves,R.,&Zerovnik,J.(2016).Mixedconnectivityof Cartesiangraphproductsandbundles.arXiv:1002.2508 Johann, S. (2021). On Simultaneous Domination and Mixed Connectivity in Graphs Verlag Dr. Hut. https:// books.google.de/books?id=NQJ5zgEACAAJ Mader, W. (1979).Connectivity and Edge-connectivity in Finite Graphs.Surveys in Combinatorics (Proceedings of the Seventh British Combinatorial Conference), London Mathematical Society Lecture Note Series Surveys in combinatorics (proceedings of the seventh british combinatorial conference), london mathematical society lecture note series ( 38, 66–95). https://doi.org/10.1017/cbo9780511662133.005 Sadeghi, E., & Fan, N. (2019). On the survivable network design problem with mixed connectivity requirements. Annals of Operations Research.https://doi.org/10.1007/s10479-019-03175-5 Streicher, M. (2021). Uncertainty in Discrete Optimization: Connectivity and Covering PhD ThesisTechnische Universitätät Kaiserslautern. https://doi.org/10.26204/KLUEDO/6555 West, D. B. (2001). Introduction to Graph Theory (2). Prentice-Hall. Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. 123