### Abstract

Let G be a graph and let s be a vertex of G. We consider the structure of the set of all lifts of two edges incident with s that preserve edge-connectivity. Mader proved that two mild hypotheses imply there is at least one pair that lifts, while Frank showed (with the same hypotheses) that there are at least (deg(s) - 1)/2 disjoint pairs that lift. We consider the lifting graph: its vertices are the edges incident with s, two being adjacent if they form a liftable pair. We have three main results, the first two with the same hypotheses as for Mader’s Theorem.

(i)Let F be a subset of the edges incident with s. We show that F is independent in the lifting graph of G if and only if there is a single edge-cut C in G of size at most r + 1 containing all the edges in F, where r is the maximum number of edge-disjoint paths from a vertex (not s) in one component of G - C to a vertex (not s) in another component of G - C.

(ii)In the k-lifting graph, two edges incident with s are adjacent if their lifting leaves the resulting graph with the property that any two vertices different from s are joined by k pairwise edge-disjoint paths. If both deg(s) and k are even, then the k-lifting graph is a connected complete multipartite graph. In all other cases, there are at most two components. If there are exactly two components, then each component is a complete multipartite graph. If deg(s) is odd and there are two components, then one component is a single vertex.

(iii)Huck proved that if k is odd and G is (k+1)-edge-connected, then G is weakly k-linked (that is, for any k pairs ⟨x

P

(i)Let F be a subset of the edges incident with s. We show that F is independent in the lifting graph of G if and only if there is a single edge-cut C in G of size at most r + 1 containing all the edges in F, where r is the maximum number of edge-disjoint paths from a vertex (not s) in one component of G - C to a vertex (not s) in another component of G - C.

(ii)In the k-lifting graph, two edges incident with s are adjacent if their lifting leaves the resulting graph with the property that any two vertices different from s are joined by k pairwise edge-disjoint paths. If both deg(s) and k are even, then the k-lifting graph is a connected complete multipartite graph. In all other cases, there are at most two components. If there are exactly two components, then each component is a complete multipartite graph. If deg(s) is odd and there are two components, then one component is a single vertex.

(iii)Huck proved that if k is odd and G is (k+1)-edge-connected, then G is weakly k-linked (that is, for any k pairs ⟨x

_{i}; y_{i}⟩, there are k edge-disjoint paths P_{i}, withP

_{i}joining x_{i}and y_{i}). We use our results to extend a slight weakening of Huck’s theorem to some infinite graphs: if k is odd, every (k + 2)-edge-connected, locally finite, 1-ended, infinite graph is weakly k-linked.Original language | English |
---|---|

Journal | Graphs and Combinatorics |

Volume | 32 |

Issue number | 6 |

Pages (from-to) | 2575-2589 |

ISSN | 0911-0119 |

DOIs | |

Publication status | Published - 2016 |

### Keywords

- Edge-connectivity
- Lifting

## Cite this

Ok, S., Richter, R. B., & Thomassen, C. (2016). Liftings in Finite Graphs and Linkages in Infinite Graphs with Prescribed Edge-Connectivity.

*Graphs and Combinatorics*,*32*(6), 2575-2589. https://doi.org/10.1007/s00373-016-1724-9