betaFeedback

WorksMathematics

Full immersions in Eulerian group-labeled graphs

Abstract

An immersion of a graph H in a graph G is full if the immersion uses every edge of G. We give a structure theorem for group-labeled Eulerian graphs excluding a fixed group-labeled graph as a full immersion.

Introduction

In this paper, we extend the well-developed theory of structure theorems for graphs excluding a fixed immersion to what we call full immersions in group labeled graphs. A primary goal in doing so is to develop tools for analyzing vertex minors in graphs which are obtained from circle graphs by adding a fixed number of vertices arbitrarily attached to the rest of the circle graph.

All graphs in this paper are finite and possibly have both loops and parallel edges. A graph GG contains a graph HH as an immersion if there exists a function ϕ\phi whose domain is V(H)∪E(H)V(H) \cup E(H) such that:

  1. ϕ(v)∈V(G)\phi(v) \in V(G) and ϕ(v)≠ϕ(u)\phi(v) \ne\phi(u) for all u,v∈V(H)u,v \in V(H), u≠vu \ne v;

  1. for all edges e∈E(H)e \in E(H) with distinct ends uu and vv, ϕ(e)\phi(e) is a walk with endpoints ϕ(u)\phi(u) and ϕ(v)\phi(v); for all loops e∈E(H)e \in E(H) attaching to the vertex vv, ϕ(e)\phi(e) is a non-empty closed walk which starts and ends at ϕ(v)\phi(v);

  1. For every edge e∈E(H)e \in E(H), the walk ϕ(e)\phi(e) uses each edge at most once; for all distinct edges e,f∈E(H)e, f \in E(H), the walks ϕ(e)\phi(e) and ϕ(f)\phi(f) are pairwise edge disjoint.

The vertices {ϕ(v):v∈V(H)}\{\phi(v) : v \in V(H)\} are the branch vertices of the immersion, and the walks ϕ(e)\phi(e) for e∈E(H)e \in E(H) are denoted the branch walks. In the literature, a distinction is made between weak and strong immersions, where strong immersions have the additional requirement that no branch vertex be contained as an internal vertex of a branch walk. However, for our purposes here, we make no such distinction and use immersion to refer to what has historically been called weak immersion. Immersions were introduced by Nash-Williams in [12] where he conjectured that graphs are well quasi-ordered under immersion containment. As part of their graph minors series, Robertson and Seymour affirmed the conjecture [16] and general structure theorems for graphs excluding a fixed immersion were independently proven in [4, 19].

We present a structure theorem for excluded full immersions in group labeled graphs. An immersion of a graph HH in a graph GG is full if every edge of GG is contained in the union of the edge sets of the branch walks.

Given a group Γ\Gamma, a Γ\Gamma-labeled graph is an undirected graph where each edge ee is assigned both an orientation and a label αe\alpha_e in Γ\Gamma. Informally, when considering immersions in group-labeled graphs, the sequence of edges in a branch walk has a weight in Γ\Gamma obtained by the product of the weights on the edges of the walk, where for each edge ee on the walk, we right-multiply by αe\alpha_e when traversing an edge ee according to the orientation, and right-multiply by αe−1\alpha_e^{-1} when traversing the edge contrary to the orientation. Some care is needed to rigorously deal with the orientations and we give the exact definition below. Group-labeled graphs have been used in a number of contexts: graph embeddings and coverings [8, 9], symmetry-forced rigidity [1, 10, 18] (i.e., bar and joint frameworks where every non-rigid motion breaks a specified symmetry), as well as structural [5, 7, 17] and extremal [13, 14] properties of matroids.

A primary motivation for studying full immersions in Eulerian group-labeled graphs comes from the structure theory of excluded vertex minors. A circle graph is the intersection graph of a family of chords of a circle. Circle graphs play a central role in the area, including Bouchet’s characterization by excluded vertex minors [3] and the vertex-minor grid theorem [6]. Equivalently, for a circle graph GG there exists a 4-regular multigraph G‾\overline{G} with V(G)=V(G‾)V(G) = V(\overline{G}) for which a fixed Eulerian tour encodes the adjacencies in GG: two vertices are adjacent in GG exactly when their occurrences alternate along the tour [2, 15]. In this representation, local complementation at a vertex vv corresponds to changing the Euler tour by rerouting at the vertex vv, and vertex-minor containment in GG is reflected by full immersion in the corresponding 4-regular graphs. This correspondence extends naturally to graphs obtained from circle graphs by adding vertices with arbitrary neighborhoods. Consider a graph G+G^{+} obtained by adding a vertex xx to GG with an arbitrary neighborhood in GG. The neighborhood of xx can be encoded by a Z2\mathbb{Z}_2-labeling of the edges of G‾\overline{G}, with adjacency determined by the parity of the sum of the labels along the portion of the Euler tour between the two occurrences of a vertex. Labeled full immersions in the labeled G‾\overline{G} then allow us to study vertex-minors within G+G^+. For graphs obtained by adding kk vertices to the circle graph GG, we can again encode their neighborhoods coordinatewise by labels in Z2k\mathbb{Z}_2^k in G‾\overline{G}. Thus, full immersions in group-labeled graphs provide a framework for studying vertex minors in graphs which are nearly circle graphs.

In general, we will follow standard graph theoretic notation. Given a graph GG and a set of vertices BB, we write δG(B)\delta_G(B) (or simply δ(B)\delta(B) when GG is clear from the context) for the set of all edges of GG with exactly one end in BB. If BB consists of a single vertex vv, we write δ(v)\delta(v). We will use E(B)E(B) to refer to the set E(G[B])E(G[B]). For a set XX and x∈Xx \in X, we will use the notation X−xX-x for X∖{x}X \setminus\{x\}.

Group-labeled Graphs

We now introduce the notation to work with orientations of edges in group labeled graphs. Given a graph GG, for each edge ee of GG we define two distinct oriented edges which we denote by e⃗\vec{e} and e⃗−1\vec{e}^{-1}. We call ee the underlying edge of an oriented edge e⃗\vec{e} and will refer to e⃗\vec{e} as an orientation of the edge ee. An oriented edge e⃗\vec{e} has a tail and a head, each of which is an endpoint of the underlying edge ee. If ee has two distinct endpoints, then the head and tail are distinct vertices. Moreover, it holds for all oriented edges e⃗\vec{e} that the head of e⃗\vec{e} is equal to the tail of e⃗−1\vec{e}^{-1}. We say that e⃗\vec{e} is oriented from its tail to its head. We write E⃗(G)\vec{E}(G) for the set of all oriented edges arising from the edges of GG. Depending on the context, we will want to consider the degree of a vertex either taking into account possible loops or not. To that end, we adopt the following convention. The degree of a vertex vv, denoted deg⁡(v)\deg(v), is ∣δ(v)∣|\delta(v)| plus twice the number of loops incident to vv. We will use d(v)d(v) as notation to indicate ∣δ(v)∣|\delta(v)|. Note that deg⁡(v)\deg(v) and d(v)d(v) always have the same parity, regardless of the presence of loops.

Let Γ\Gamma be a group. We denote the group operation multiplicatively and the identity by 11. A Γ\Gamma-labeling of a graph GG is a function γ:E⃗(G)→Γ\gamma: \vec{E}(G) \to\Gamma such that γ(e⃗−1)=γ(e⃗)−1\gamma(\vec{e}^{-1}) = \gamma(\vec{e})^{-1} for any edge e⃗\vec{e} of GG. We call γ(e⃗)\gamma(\vec{e}) the label of an oriented edge e⃗\vec{e}. Throughout the article, we adopt the convention that γ(∅)=1\gamma(\emptyset) = 1 for any labeling function γ\gamma. A Γ\Gamma-labeled graph is a pair (G,γ)(G,\gamma) where GG is a graph and γ\gamma is a Γ\Gamma-labeling of GG. There is an equivalence relation on Γ\Gamma-labelings defined as follows. Given a Γ\Gamma-labeled graph (G,γ)(G,\gamma), a vertex x∈V(G)x \in V(G), and a group element α∈Γ\alpha\in\Gamma, shifting by α\alpha at xx means to append α\alpha at the beginning of the label of each oriented edge with tail xx and to append α−1\alpha^{-1} at the end of the label of each oriented edge with head xx. Thus, if e⃗\vec{e} is an oriented loop at xx, then its new label after shifting is αγ(e⃗)α−1\alpha\gamma(\vec{e})\alpha^{-1}. Likewise, if e⃗\vec{e} is an oriented edge whose tail is xx and whose head is not xx, then its new label is αγ(e⃗)\alpha\gamma(\vec{e}). This is the inverse of γ(e⃗−1)α−1\gamma(\vec{e}^{-1})\alpha^{-1}, which is the new label of e⃗−1\vec{e}^{-1}. We say that a Γ\Gamma-labeling γ′\gamma' of GG is a shifting of γ\gamma if it can be obtained by a (finite) sequence of such shifts.

A trail TT in a graph GG is a sequence of oriented edges e⃗1e⃗2⋯e⃗n\vec{e}_1\vec{e}_2\cdots\vec{e}_n, n≥1n \ge1, such that the underlying edges are all distinct, and for each i∈[n−1]i \in[n-1], the head of e⃗i\vec{e}_i equals the tail of e⃗i+1\vec{e}_{i+1}. Note that the endpoints of the edges need not be distinct; the same vertex may be visited multiple times. The tail of TT is the tail of e⃗1\vec{e}_1 and the head of TT is the head of e⃗n\vec{e}_n. We call the head and tail of TT its ends. We use V(T)V(T) to refer to the set of vertices which are either heads or tails of oriented edges in TT. We write E(T)E(T) to refer to the undirected edges of GG which are the underlying edges of oriented edges contained in TT. We say two trails T1T_1 and T2T_2 are edge disjoint if E(T1)∩E(T2)=∅E(T_1) \cap E(T_2) = \varnothing. Given a group-labeling γ\gamma of GG, the label of TT is γ(T)=γ(e⃗1)γ(e⃗2)⋯γ(e⃗n)\gamma(T) = \gamma(\vec{e}_1)\gamma(\vec{e}_2)\cdots\gamma(\vec{e}_n). The inverse of TT is the trail T−1T^{-1} which is the sequence of edges in the reverse order and with the reverse orientation. Thus γ(T−1)=γ(T)−1\gamma(T^{-1}) = \gamma(T)^{-1}. The transitions of TT are the ordered pairs (e⃗i,e⃗i+1)(\vec{e}_i,\vec{e}_{i+1}) for i∈[n−1]i \in[n-1]. Thus TT has n−1n-1 transitions. We view transitions of the form (e⃗1,e⃗2)(\vec{e}_1,\vec{e}_2) and (e⃗2−1,e⃗1−1)(\vec{e}_2^{-1},\vec{e}_1^{-1}) as being equivalent; thus T−1T^{-1} has the same transitions as TT.

Immersions

We now extend the definition of immersions to group-labeled graphs.

Let Γ\Gamma be a group. We say that a Γ\Gamma-labeled graph (G,γG)(G,\gamma_G) admits an immersion of a Γ\Gamma-labeled graph (H,γH)(H,\gamma_H) if there exist a shifting γG′\gamma'_G of γG\gamma_G and a function φ\varphi which injectively maps V(H)V(H) to V(G)V(G) and which maps E⃗(H)\vec{E}(H) to trails in GG such that

  1. for any oriented edge e⃗∈E⃗(H)\vec{e} \in\vec{E}(H), the trails φ(e⃗)\varphi(\vec{e}) and φ(e⃗−1)\varphi(\vec{e}^{-1}) are inverses,

  2. for any distinct edges e1e_1 and e2e_2 of HH, the trails φ(e⃗1)\varphi(\vec{e}_1) and φ(e⃗2)\varphi(\vec{e}_2) are edge-disjoint, and

  3. for any oriented edge e⃗\vec{e} of HH, the tail of e⃗\vec{e} is mapped to the tail of φ(e⃗)\varphi(\vec{e}), the head of e⃗\vec{e} is mapped to the head of φ(e⃗)\varphi(\vec{e}), and γH(e⃗)=γG′(φ(e⃗))\gamma_H(\vec{e}) = \gamma'_G(\varphi(\vec{e})).

We say that φ\varphi is an immersion of (H,γH)(H,\gamma_H) into (G,γG)(G,\gamma_G). As in the case of undirected graphs, we call the image of V(H)V(H) under φ\varphi the branch vertices and the image of E⃗(H)\vec{E}(H) under φ\varphi the branch trails. The transitions of an immersion are the transitions of its branch trails. The labeling γG′\gamma'_G is an accommodating labeling of the immersion; in general, an accommodating labeling will not necessarily be unique.

A graph GG contains a graph HH as a near-full immersion if there is an HH-immersion φ\varphi such that there is at most one non-trivial component CC after deleting edges of ⋃e∈E(H)E(φ(e))\bigcup_{e \in E(H)} E(\varphi(e)) in GG, and moreover, the component CC, if it exists, contains a branch vertex of HH. For a vertex x∈V(H)x \in V(H), if the component CC, when it exists, contains the vertex φ(x)\varphi(x), we say GG contains HH as an xx-near-full immersion. The definition extends analogously to group labeled immersions.

Observation 1.1. If (G1,γ1)(G_1,\gamma_1) has an xx-near-full immersion φ2\varphi_2 of (G2,γ2)(G_2,\gamma_2), and (G2,γ2)(G_2,\gamma_2) has a yy-near-full immersion φ3\varphi_3 of (G3,γ3)(G_3,\gamma_3) with φ3(y)=x\varphi_3(y) = x, then (G1,γ1)(G_1,\gamma_1) has a yy-near-full immersion of (G3,γ3)(G_3,\gamma_3).

Our primary tool in proving the structure theorem for excluded full immersions in Eulerian group labeled graphs is the following theorem which says that excluding a fixed near-full immersion implies excluding some larger group labeled immersion with no further requirements on the edge set which it utilizes.

Theorem 1.2. Let Γ\Gamma be a finite group. For every Γ\Gamma-labeled graph (H,γH)(H,\gamma_H) there exists a Γ\Gamma-labeled graph (H′,γH′)(H',\gamma_{H'}) such that for every Eulerian 4-edge-connected Γ\Gamma-labeled graph (G,γG)(G,\gamma_G) and for every vertex x∈V(H)x \in V(H), if (G,γG)(G,\gamma_G) contains (H′,γH′)(H',\gamma_{H'}) as an immersion, then (G,γG)(G,\gamma_G) contains (H,γH)(H,\gamma_H) as an xx-near-full immersion.

The structure theorem

The structure theorem for Eulerian group-labeled graphs excluding a fixed graph as a full immersion builds on the structure of graphs excluding a group-labeled immersion. We give the notation necessary to state the structure theorem for excluded group-labeled immersions (without the requirement that they be nearly full), and then present the statement for excluded full group-labeled immersions.

A tree-cut decomposition of a graph GG is a pair (T,B)(T,\mathcal{B}) such that TT is a tree and B=(Bt:t∈V(T))\mathcal{B}=(B_t:t\in V(T)) is a collection of pairwise-disjoint (possibly empty) subsets of V(G)V(G) whose union is V(G)V(G). The sets in B\mathcal{B} are the bags of the decomposition.

Roughly, the structure theorem for excluded group-labeled immersions says that each bag either 1) has a “torso” with few high degree vertices, or 2) has “almost all of its edges” labeled over a proper subgroup.

So, let GG be a graph, and let (T,B)(T,\mathcal{B}) be a tree-cut decomposition of GG. Given a bag Bt∈BB_t\in\mathcal{B}, the torso of BtB_t is the graph HH obtained from GG as follows. Let T1,…,TℓT_1,\ldots,T_\ell be the components of T∖tT\setminus t. For each i∈[ℓ]i\in[\ell], let Vi=⋃s∈V(Ti)BsV_i=\bigcup_{s\in V(T_i)}B_s. Then HH is created by identifying each non-empty set ViV_i to a single vertex, which we call a new vertex of the torso. We keep parallel edges, but we remove any loops at the new vertices.

Now, let Γ\Gamma be a group, let (G,γ)(G,\gamma) be a Γ\Gamma-labeled graph, and let B⊆V(G)B\subseteq V(G). Then a certificate for BB is a tuple (X,γ′)(X,\gamma') so that XX is a set of edges of GG with δ(B)⊆X⊆δ(B)∪E(B)\delta(B)\subseteq X\subseteq\delta(B)\cup E(B) and γ′\gamma' is a shifting of γ\gamma so that the γ′\gamma'-labels of orientations of the edges in E(B)∖XE(B)\setminus X generate a proper subgroup of Γ\Gamma. The value of a certificate is

val⁡(X,γ′)=∣δ(B)∣+2∣X∩E(B)∣.\operatorname{val}(X,\gamma')=|\delta(B)|+2|X\cap E(B)|.

This counts the edges of XX, except edges with both ends in BB are counted twice.

Theorem 1.3 ([11]). For any finite group Γ\Gamma and positive integers kk and nn, there is an integer t=4kn∣Γ∣6+⌊log⁡2∣Γ∣⌋t=4kn|\Gamma|^{6+\lfloor\log_2|\Gamma|\rfloor} so that the following holds for any 2-edge-connected Γ\Gamma-labeled graph (G,γ)(G,\gamma) which forbids an immersion of some nn-vertex Γ\Gamma-labeled graph where each vertex is incident to at most kk edges. There exist a shifting γ′\gamma' of γ\gamma and a tree-cut decomposition (T,B)(T,\mathcal{B}) of GG such that for every bag B∈BB\in\mathcal{B}, at least one of the following holds.

  1. There are at most n∣Γ∣n|\Gamma| vertices in the torso of BB of degree greater than tt, and none of them are the new vertices of the torso.

  1. There exists X⊆E(G)X \subseteq E(G) so that (X,γ′)(X,\gamma') is a certificate for BB of value at most tt.

We are now able to state the structure theorem for excluded full group labeled immersions in Eulerian graphs. The theorem finds the same structure as Theorem 1.3 unless the total edge labels of GG and HH differ in an elementary abelian 22-group quotient of Γ\Gamma.

Theorem 1.4. Let Γ\Gamma be a finite group. For every Eulerian Γ\Gamma-labeled graph (H,γH)(H,\gamma_H) with at least one edge, there exists a positive integer t=t(Γ,H)t=t(\Gamma,H) such that the following holds. Let (G,γG)(G,\gamma_G) be a 44-edge-connected Eulerian Γ\Gamma-labeled graph with no (H,γH)(H,\gamma_H) full immersion. Then one of the following holds.

  1. There exists a normal subgroup Γ′\Gamma' of Γ\Gamma such that Γ/Γ′\Gamma/\Gamma' is isomorphic to Z2r\mathbb{Z}_2^r for some nonnegative integer rr, and over this quotient labeling the sum of the edge labels in (G,γG)(G,\gamma_G) differs from that in (H,γH)(H,\gamma_H).

  1. There exist a shifting γ~\widetilde{\gamma} of γG\gamma_G and a tree-cut decomposition (T,B)(T,\mathcal{B}) of GG such that for every bag B∈BB \in\mathcal{B}, at least one of the following holds.

(a) There are at most tt vertices in the torso of BB of degree greater than tt, and none of them are the new vertices of the torso.

(b) There exists X⊆E(G)X \subseteq E(G) such that (X,γ~)(X,\widetilde{\gamma}) is a certificate for BB of value at most tt.

The proof of Theorem 1.4 is presented in § 4.

Outline

The paper is organized as follows. In § 2, we present Theorem 2.1 showing that if a 44-edge-connected Γ\Gamma-labeled Eulerian graph has many edge disjoint circuits sharing a common vertex xx each with label not in a fixed subgroup Γ′\Gamma' of Γ\Gamma, then the edge set of the whole graph can be partitioned into edge disjoint circuits through xx each with label outside Γ′\Gamma'. This packing result is used in § 3 to prove Theorem 1.2 which states that excluding a fixed group-labeled (H,γH)(H,\gamma_H) as a near-full immersion in a 44-edge-connected Eulerian graph (G,γG)(G,\gamma_G) implies that (G,γG)(G,\gamma_G) does not contain a larger (H′,γH′)(H',\gamma_{H'}) as a group labeled immersion without the requirement that it be nearly full. Already, Theorem 1.2 together with Theorem 1.3 yields a structure theorem for excluded near-full immersions in 44-edge-connected group-labeled Eulerian graphs. Finally, in § 4, we determine when a near-full immersion can be extended to a full immersion, providing the final ingredient needed to prove Theorem 1.4.

Decomposing to circuits labeled outside of a subgroup

Let Γ\Gamma be a group, let Γ′\Gamma' be a subgroup of Γ\Gamma, let (G,γ)(G,\gamma) be a Γ\Gamma-labeled graph, and let xx be a vertex of GG.

A circuit in GG is a trail whose head and tail are equal; we say that it begins and ends at that vertex. Given a vertex xx of GG, an xx-packing of GG is a collection C\mathcal{C} of pairwise edge-disjoint circuits so that each circuit begins and ends at xx. We say that the xx-packing saturates xx if ∣C∣=deg⁡(x)/2|\mathcal{C}|=\deg(x)/2. We call an xx-packing an (x,Γ′)(x,\Gamma')-packing if every circuit has label outside of Γ′\Gamma'. Similarly, an (x,Γ′)(x,\Gamma')-decomposition is an (x,Γ′)(x,\Gamma')-packing C\mathcal{C} so that every edge of GG is in E(T)E(T) for some T∈CT\in\mathcal{C}.

This section is dedicated to proving the following theorem.

Theorem 2.1. Let k≥1k\ge1 be a positive integer. Let Γ\Gamma be a group, let Γ′\Gamma' be a subgroup of Γ\Gamma, let (G,γ)(G,\gamma) be a Γ\Gamma-labeled Eulerian graph which is 4-edge-connected, and let xx be a vertex of GG such that there exists an (x,Γ′)(x,\Gamma')-packing of size kk. Then there exists an (x,Γ′)(x,\Gamma')-decomposition of size at least ⌈k/2⌉\lceil k/2\rceil.

We proceed to introduce the set-up needed to establish Theorem 2.1 above. Fix an Eulerian, 4-edge-connected Γ\Gamma-labeled graph (G,γ)(G,\gamma), a vertex x∈V(G)x\in V(G), and an xx-packing C\mathcal{C} which saturates xx. We refer to each nontrivial connected component of G−⋃C∈CE(C)G-\bigcup_{C\in\mathcal{C}}E(C) as an unused component of C\mathcal{C}. Note each unused component is an Eulerian subgraph of GG. We write comp⁡G(C)\operatorname{comp}_{G}(\mathcal{C}) for the auxiliary bipartite graph whose vertices in one part are the circuits in C\mathcal{C}, in the other the unused components of C\mathcal{C}, and vertices in distinct parts are adjacent if and only if the corresponding parts share a vertex. Whenever GG is clear from the context we drop the subscript. Given a vertex XX of comp⁡(C)\operatorname{comp}(\mathcal{C}) we write deg⁡C(X)\deg_{\mathcal{C}}(X) for the degree of XX in comp⁡(C)\operatorname{comp}(\mathcal{C}); whenever we speak of the degree of a circuit or an unused component we implicitly mean their degree in comp⁡(C)\operatorname{comp}(\mathcal{C}).

Let HH be an unused component of C\mathcal{C} of degree one, and C∈CC\in\mathcal{C} the unique circuit which contains a vertex of HH. We define the closure of HH, denoted by cl⁡(H)\operatorname{cl}(H), to be a containment minimal set S⊆V(G)−xS\subseteq V(G)-x so that V(H)⊆SV(H)\subseteq S and δ(S)\delta(S) contains at most two edges in CC. Observe that this notion is well-defined given C\mathcal{C} saturates xx and thus V(G)−xV(G)-x contains V(H)V(H) and δ(V(G)−x)\delta(V(G)-x) intersects CC in exactly two edges. Moreover, if S,S′⊆V(G)−xS,S'\subseteq V(G)-x both contain V(H)V(H) and satisfy ∣δ(S)∩E(C)∣=∣δ(S′)∩E(C)∣=2|\delta(S)\cap E(C)|=|\delta(S')\cap E(C)|=2, then so does S∩S′S\cap S'. To see this, notice that S∩S′S\cap S' must contain V(H)V(H) and not xx, and if E(C)E(C) has an edge in δ(S∩S′)\delta(S\cap S'), then it has at least two edges in δ(S∪S′)\delta(S\cup S') because it is an xx-circuit. By submodularity of the cut-function, the number of edges of CC in δ(S∩S′)\delta(S\cap S') is at most two, as required. It follows that cl⁡(H)\operatorname{cl}(H) is uniquely defined. Finally, we note that cl⁡(H)⊆V(H)∪V(C)\operatorname{cl}(H)\subseteq V(H)\cup V(C) as deleting any vertex not contained in either HH or CC does not change how many boundary edges intersect E(C)E(C).

We call an unused component HH of C\mathcal{C} of degree one flexible if the unique circuit C∈CC\in\mathcal{C} incident to HH in comp⁡(C)\operatorname{comp}(\mathcal{C}) is also of degree one in the auxiliary graph.

Symmetrically, we call HH inflexible if CC has degree at least two. An important consequence of the former definition is that cl⁡(H)\operatorname{cl}(H) always intersects some other circuit in the packing whenever HH is flexible. We formalize this in the lemma below.

Lemma 2.2. Let (G,γ)(G,\gamma) be a 4-edge-connected Eulerian group-labeled graph, x∈V(G)x \in V(G) a vertex of GG, C\mathcal{C} an xx-packing which saturates xx, and HH a flexible unused component of C\mathcal{C} that is adjacent to C∈CC \in\mathcal{C} in comp⁡(C)\operatorname{comp}(\mathcal{C}). Then there is some C′∈CC' \in\mathcal{C} different from CC such that cl⁡(H)∩V(C′)≠∅\operatorname{cl}(H) \cap V(C') \ne\varnothing.

Proof. Consider the cut δ(cl⁡(H))\delta(\operatorname{cl}(H)). Since this contains at most two edges in CC and GG is 4-edge-connected, there exists a trail TT in GG from xx to cl⁡(H)\operatorname{cl}(H), internally disjoint from {x}∪cl⁡(H)\{x\} \cup\operatorname{cl}(H), that is edge-disjoint from E(C)∩δ(cl⁡(H))E(C) \cap\delta(\operatorname{cl}(H)). Consider the last oriented edge e⃗\vec{e} of TT with underlying edge ee and head vv contained in cl⁡(H)\operatorname{cl}(H). The edge ee cannot lie in E(C)E(C) by definition, nor in HH because V(H)⊆cl⁡(H)V(H) \subseteq\operatorname{cl}(H). Evidently, the edge ee cannot lie in a different unused component of C\mathcal{C}, since in that case vv must either lie in V(C)V(C) implying that the degree of CC in comp⁡(C)\operatorname{comp}(\mathcal{C}) is at least two, contradicting our assumptions, or lie in V(H)V(H) contrary to HH being a component. We conclude that there exists some other circuit C′∈CC' \in\mathcal{C} such that e∈E(C′)e \in E(C') and thus V(C′)V(C') has a vertex in cl⁡(H)\operatorname{cl}(H). □

Dually to the closure, we consider the notion of an ear decomposition of HH into CC. This is a sequence T0:=H,T1,…,TkT_0 := H,T_1,\ldots,T_k so that

  1. for each i∈{1,…,k}i \in\{1,\ldots,k\}, TiT_i is a non-empty subtrail of C−xC-x that is edge-disjoint from ⋃j=0i−1E(Tj)\bigcup_{j=0}^{i-1} E(T_j) with both ends in ⋃j=0i−1V(Tj)\bigcup_{j=0}^{i-1} V(T_j); and

  2. for each i∈{1,…,k}i \in\{1,\ldots,k\}, the sequence T1,…,TiT_1,\ldots,T_i can be reordered into a subtrail of C−xC-x.

Note that we allow each TiT_i to be a circuit. We call T1,…,TkT_1,\ldots,T_k the ears of this decomposition. We say that the ear decomposition is maximal if there is no trail Tk+1T_{k+1} so that H,T1,…,Tk,Tk+1H,T_1,\ldots,T_k,T_{k+1} is also an ear decomposition of HH into CC. The lemma below establishes that the notion of a maximal ear decomposition is dual to the closure.

Lemma 2.3. Let (G,γ)(G,\gamma) be a 4-edge-connected Eulerian group-labeled graph, x∈V(G)x \in V(G) a vertex of GG, C\mathcal{C} an xx-packing saturating xx, and HH an unused component of C\mathcal{C} of degree one adjacent to C∈CC \in\mathcal{C} in comp⁡(C)\operatorname{comp}(\mathcal{C}). If T0:=H,T1,…,TkT_0 := H,T_1,\ldots,T_k is a maximal ear decomposition of HH into CC, then ⋃j=0kV(Tj)=cl⁡(H)\bigcup_{j=0}^{k} V(T_j) = \operatorname{cl}(H).

Proof. We first show that ⋃j=0iV(Tj)⊆cl⁡(H)\bigcup_{j=0}^{i} V(T_j) \subseteq\operatorname{cl}(H) by induction on ii; this holds for i=0i=0 since V(H)⊆cl⁡(H)V(H) \subseteq\operatorname{cl}(H) by definition. Assuming ⋃j=0iV(Tj)⊆cl⁡(H)\bigcup_{j=0}^{i} V(T_j) \subseteq\operatorname{cl}(H), then since Ti+1T_{i+1} is a subtrail of C−xC-x which is disjoint from the previous ears, and δ(cl⁡(H))\delta(\operatorname{cl}(H)) contains at most two edges from CC, it must be that V(Ti+1)⊆cl⁡(H)V(T_{i+1}) \subseteq\operatorname{cl}(H) as needed. Indeed otherwise δ(cl⁡(H))\delta(\operatorname{cl}(H)) contains at least two edges in E(Ti+1)E(T_{i+1}) as well as the first and last edge of E(C)E(C) with an end in cl⁡(H)\operatorname{cl}(H). Fix U=V(H)∪⋃i=1kV(Ti)U = V(H) \cup\bigcup_{i=1}^{k} V(T_i). By the previous paragraph, U⊆cl⁡(H)U \subseteq\operatorname{cl}(H). Let T1′,…,Tk′T'_1,\ldots,T'_k be an ordering of the sequence T1,…,TkT_1,\ldots,T_k such that T′:=T1′…Tk′T' := T'_1\ldots T'_k is a subtrail of C−xC-x. If a vertex in UU occurs along C−xC-x before the beginning of T′T', let Tk+1T_{k+1} be the subtrail of C−xC-x from the last such occurrence to the beginning of T′T'. Then T0,T1,…,Tk+1T_0,T_1,\ldots,T_{k+1} is an ear decomposition of HH into CC violating our choice of a maximal ear decomposition. Similarly, if a vertex of UU occurs along C−xC-x strictly after the end of T′T', we again get a contradiction to the maximality of our ear decomposition. We conclude that the occurrences of vertices of UU along CC form exactly the interval occupied by T′T', and therefore ∣δ(U)∩E(C)∣=2|\delta(U)\cap E(C)|=2. As V(H)⊆UV(H)\subseteq U, it follows that cl⁡(H)⊆U\operatorname{cl}(H)\subseteq U, completing the proof.

We note that while the above establishes that the underlying set of vertices in the maximal ear decomposition is unique, the number kk of ears or their order T1,…,TkT_1,\ldots,T_k is not necessarily unique. However, this notion still gives rise to a meaningful way of measuring the complexity of unused components of degree one in an xx-packing, which we now define.

For a flexible unused component HH of CC adjacent to C∈CC\in\mathcal{C} in comp⁡(C)\operatorname{comp}(C), we let the rank of HH in CC, denoted by rank⁡C(H)\operatorname{rank}_C(H), be the minimum i∈Ni\in\mathbb{N} such that there is a maximal ear decomposition T0,T1,…,TkT_0,T_1,\ldots,T_k of HH into CC and some C′∈CC'\in\mathcal{C} different from CC with the property that V(Ti)∩V(C′)≠∅V(T_i)\cap V(C')\ne\varnothing. For flexible unused components Lemmas 2.2 and 2.3 imply that such ii always exists, and also by definition rank⁡C(H)≥1\operatorname{rank}_C(H)\ge1. For an inflexible unused component HH of CC we define rank⁡C(H)=∞\operatorname{rank}_C(H)=\infty. Furthermore, we define the rank of CC, denoted by rank⁡(C)\operatorname{rank}(C), to be the minimum of rank⁡C(H)\operatorname{rank}_C(H) over all unused components HH of CC of degree one if there is at least one such component, and 0 otherwise.

We are now ready to proceed with the proof of the main theorem of this section which we repeat here for convenience.

Theorem 2.1. Let k≥1k\ge1 be a positive integer. Let Γ\Gamma be a group, let Γ′\Gamma' be a subgroup of Γ\Gamma, let (G,γ)(G,\gamma) be a Γ\Gamma-labeled Eulerian graph which is 4-edge-connected, and let xx be a vertex of GG such that there exists an (x,Γ′)(x,\Gamma')-packing of size kk. Then there exists an (x,Γ′)(x,\Gamma')-decomposition of size at least ⌈k/2⌉\lceil k/2\rceil.

To briefly summarize the argument, under the theorem’s assumptions, we show there is an xx-packing C\mathcal{C} with the property that every circuit has degree at most one and every unused component has degree at least two in comp⁡(C)\operatorname{comp}(\mathcal{C}). Consequently, this leads to a small number of unused components which can be greedily absorbed in the packing.

Proof of Theorem 2.1. We choose an xx-packing C\mathcal{C} in (G,γ)(G,\gamma) subject to the following conditions, satisfied in the order listed below:

  1. C\mathcal{C} contains exactly deg⁡(x)2\frac{\deg(x)}{2} many circuits and at least kk of these have labels outside of Γ′\Gamma';

  1. the number of edges covered by CC is maximized;

  1. the number of unused components of CC of degree at least two is maximized;

  1. the rank of CC is minimized.

In general, any xx-circuit CC with group value not in Γ′\Gamma' which visits xx internally can be decomposed into two distinct xx-circuits, at least one of which has group value not in Γ′\Gamma'. Along with the fact that GG is Eulerian, we conclude that there exists an xx-packing C\mathcal{C} which satisfies property 1 and, consequently, properties 1-4. The assumptions of Theorem 2.1 imply that there exists such a collection; we proceed to prove a few claims about its structure.

Claim: deg⁡C(C)=0\deg_{\mathcal{C}}(C)=0 for all circuits C∈CC\in\mathcal{C} with γ(C)∈Γ′\gamma(C)\in\Gamma'.

Proof: Let C∈CC\in\mathcal{C} satisfy γ(C)∈Γ′\gamma(C)\in\Gamma' and assume for a contradiction that there is some unused component HH which shares a vertex with CC. Let C′C' be the circuit obtained by joining an Eulerian tour of HH to CC at a common vertex, and C′\mathcal{C}' the collection obtained from C\mathcal{C} by swapping CC with C′C'. It follows that C′\mathcal{C}' still satisfies condition 1 while the number of edges covered by C′\mathcal{C}' is now strictly larger; contradiction. It follows that deg⁡C(C)=0\deg_{\mathcal{C}}(C)=0 for every C∈CC\in\mathcal{C} with γ(C)∈Γ′\gamma(C)\in\Gamma'.

Claim: deg⁡C(C)≤1\deg_{\mathcal{C}}(C)\leq1 for all circuits C∈CC\in\mathcal{C} with γ(C)∉Γ′\gamma(C)\notin\Gamma'.

Proof: Fix some C∈CC\in\mathcal{C} with γ(C)∉Γ′\gamma(C)\notin\Gamma', and assume for a contradiction that deg⁡C(C)≥2\deg_{\mathcal{C}}(C)\geq2, i.e. there are two distinct unused components H1H_1 and H2H_2 which both share vertices with CC. Suppose

C=e⃗1⋯e⃗pf⃗1e⃗p+1⋯e⃗p+ℓf⃗2e⃗p+ℓ+1⋯e⃗p+ℓ+m;C=\vec{e}_1\cdots\vec{e}_p\vec{f}_1\vec{e}_{p+1}\cdots\vec{e}_{p+\ell}\vec{f}_2\vec{e}_{p+\ell+1}\cdots\vec{e}_{p+\ell+m};

where the tail of e⃗1\vec{e}_1 is xx, the tail of f⃗1\vec{f}_1 is h1h_1 and h1∈V(C)∩V(H1)h_1\in V(C)\cap V(H_1), and the tail of f⃗2\vec{f}_2 is h2h_2 and h2∈V(C)∩V(H2)h_2\in V(C)\cap V(H_2). Let H⃗1\vec{H}_1 be an Eulerian circuit in H1H_1 starting and ending at h1h_1, and likewise define H⃗2\vec{H}_2. Consider the following elements of Γ\Gamma

a:=γ(e⃗1⋯e⃗p),b:=γ(f⃗1e⃗p+1⋯e⃗p+ℓ),a:=\gamma(\vec{e}_1\cdots\vec{e}_p),\qquad b:=\gamma(\vec{f}_1\vec{e}_{p+1}\cdots\vec{e}_{p+\ell}),
c:=γ(f⃗2e⃗p+ℓ+1⋯e⃗p+ℓ+m),χ1:=γ(H⃗1),χ2:=γ(H⃗2),c:=\gamma(\vec{f}_2\vec{e}_{p+\ell+1}\cdots\vec{e}_{p+\ell+m}),\qquad\chi_1:=\gamma(\vec{H}_1),\quad\chi_2:=\gamma(\vec{H}_2),

and observe that

(abχ2c)⋅(aχ1bχ2c)−1⋅(aχ1bc)=abc=γ(C)∉Γ′.(ab\chi_2c)\cdot(a\chi_1b\chi_2c)^{-1}\cdot(a\chi_1bc)=abc=\gamma(C)\notin\Gamma'.

It follows that one of aχ1bca\chi_1bc, abχ2cab\chi_2c, and aχ1bχ2ca\chi_1b\chi_2c must lie outside Γ′\Gamma'. We may therefore appropriately glue H1H_1, H2H_2, or both at CC to obtain a strictly bigger circuit C′C' with γ(C′)∉Γ′\gamma(C')\notin\Gamma'. By swapping CC and C′C' we obtain a new collection of circuits covering strictly more edges than before that still satisfies condition 1, giving rise to a contradiction once again. ■

Claim: deg⁡C(H)≥2\deg_{\mathcal{C}}(H)\geq2 for all unused components HH of C\mathcal{C}.

Proof: By connectivity of GG, every unused component must have degree at least one. Assume for a contradiction that there is an unused component of degree one. First

note that by the two claims above any unused component of degree one is flexible. Let HH be such a component with the property that n:=rank⁡C(H)=rank⁡(C)≥1n := \operatorname{rank}_{\mathcal{C}}(H) = \operatorname{rank}(\mathcal{C}) \ge1, i.e. its rank is minimal over all unused components of degree one. Let C∈CC \in\mathcal{C} be the unique circuit of C\mathcal{C} adjacent to HH in comp⁡(C)\operatorname{comp}(\mathcal{C}). By the first claim, we know that γ(C)∉Γ′\gamma(C) \notin\Gamma'. Moreover, fix a maximal ear decomposition T0:=H,T1,…,TkT_0 := H,T_1,\ldots,T_k of HH into CC and C′∈CC' \in\mathcal{C} distinct from CC with the property that V(Tn)∩V(C′)≠∅V(T_n) \cap V(C') \ne\varnothing. We shall construct a new xx-packing C~\widetilde{\mathcal{C}} with the property that, either the number of unused components of degree at least two is strictly larger than that of C\mathcal{C}, or it has the same number of unused components of degree at least two as C\mathcal{C} but its rank is strictly smaller than that of C\mathcal{C}; both of these lead to a contradiction to the choice of C\mathcal{C}.

Towards this goal, consider any vertex v∈V(Tn)∩V(C′)v \in V(T_n) \cap V(C'). First note that vv cannot be a vertex in ⋃i=0n−1V(Ti)\bigcup_{i=0}^{n-1} V(T_i) as this would contradict the minimality of nn; in particular, vv cannot be an endpoint of TnT_n. Choose a pair of subtrails Tn1T_n^1 and Tn2T_n^2 by arbitrarily “breaking” TnT_n at vv, i.e. non-empty subtrails of TnT_n having vv as head and tail, respectively, and satisfying Tn=Tn1Tn2T_n = T_n^1T_n^2. Since TnT_n is a subtrail of C−xC-x, we may also rewrite CC as C=C1C2C = C_1C_2, where C1C_1 is the subtrail from xx to vv containing Tn1T_n^1 and C2C_2 is a subtrail from vv to xx containing Tn2T_n^2. Similarly, we let C′=R1R2C' = R_1R_2 where R1R_1 is a subtrail of C′C' from xx to vv and R2R_2 is a subtrail of C′C' from vv to xx.

Next, we claim that at least one of the sets {C1R2,R1C2}\{C_1R_2,R_1C_2\} or {C1R1−1,C2−1R2}\{C_1R_1^{-1},C_2^{-1}R_2\} has at least as many xx-circuits labeled outside Γ′\Gamma' as the collection {C,C′}\{C,C'\}.

Consider the following elements of Γ\Gamma

a:=γ(C1),b:=γ(C2),c:=γ(R1),d:=γ(R2),a := \gamma(C_1), \qquad b := \gamma(C_2), \qquad c := \gamma(R_1), \qquad d := \gamma(R_2),

and observe that

ac−1⋅cb=ab=γ(C)∉Γ′,b−1d⋅(ad)−1=(ab)−1=γ(C)−1∉Γ′,ac^{-1}\cdot cb = ab = \gamma(C) \notin\Gamma', \qquad b^{-1}d\cdot(ad)^{-1} = (ab)^{-1} = \gamma(C)^{-1} \notin\Gamma',

and that

cb⋅b−1d=cd=γ(C′),(ad)−1⋅ac−1=(cd)−1=γ(C′)−1.cb\cdot b^{-1}d = cd = \gamma(C'), \qquad (ad)^{-1}\cdot ac^{-1} = (cd)^{-1} = \gamma(C')^{-1}.

Since γ(C)∉Γ′\gamma(C) \notin\Gamma' it follows that either ac−1=γ(C1R1−1)∉Γ′ac^{-1} = \gamma(C_1R_1^{-1}) \notin\Gamma' or cb=γ(R1C2)∉Γ′cb = \gamma(R_1C_2) \notin\Gamma'. Hence, if γ(C′)∈Γ′\gamma(C') \in\Gamma', the claimed property holds for one of the two sets {C1R2,R1C2}\{C_1R_2,R_1C_2\} or {C1R1−1,C2−1R2}\{C_1R_1^{-1},C_2^{-1}R_2\}. On the other hand, if γ(C′)∉Γ′\gamma(C') \notin\Gamma' then at least one of the two factors in all four equations above must be outside Γ′\Gamma' and again the desired property holds through a simple checking of the cases.

Let us assume without loss of generality that the claim above holds for the set {C1R2,R1C2}\{C_1R_2,R_1C_2\}. We complete the proof by showing that the collection C~\widetilde{\mathcal{C}} of xx-circuits obtained from C\mathcal{C} by replacing circuits CC and C′C' with circuits C1R2C_1R_2 and R1C2R_1C_2 yields a contradiction to the choice of C\mathcal{C}.

We first verify that the collection C~\widetilde{\mathcal{C}} is at least as good as C\mathcal{C} with respect to conditions 1, 2, and 3. Condition 1 is clearly satisfied given the previous claim. Moreover, the edges covered by C~\widetilde{\mathcal{C}} are by definition precisely the same as the edges covered by CC, and so condition 2 is also satisfied. Consider an unused component KK of CC of degree at least two. Any adjacency to a circuit other than CC and C′C' is also present in comp⁡(C~)\operatorname{comp}(\widetilde{C}), and KK cannot meet CC since otherwise K=HK=H. If KK meets C′C', then KK also meets at least one of C1R2C_1R_2 or R1C2R_1C_2. We conclude KK is of degree at least two in comp⁡(C~)\operatorname{comp}(\widetilde{C}) and condition 3 holds for C~\widetilde{C}.

There are now two cases to distinguish.

Both C1R2C_1R_2 and R1C2R_1C_2 intersect HH:​ By definition, this means that the degree of HH in comp⁡(C~)\operatorname{comp}(\widetilde{C}) is two. Combined with the observations above, this implies that C~\widetilde{C} strictly improves on condition 3 over CC which gives us the desired contradiction.

Only one of C1R2C_1R_2 and R1C2R_1C_2 intersects HH:​ By assumption, HH has degree exactly one in comp⁡(C~)\operatorname{comp}(\widetilde{C}). Since C~\widetilde{C} satisfies conditions 1–3, the first two claims hold for C~\widetilde{C} as well and we see that the unique circuit meeting HH has degree one in comp⁡(C~)\operatorname{comp}(\widetilde{C}) and label not in Γ′\Gamma'. Thus, HH is flexible and its rank is finite. In this case it must be that n=rank⁡C(H)n=\operatorname{rank}_C(H) is at least two. Indeed, if n=1n=1, then by definition of ear decompositions, the endpoint of each TiT_i for i∈[2]i\in[2] that is not vv is a vertex of HH. Therefore by construction both C1R2C_1R_2 and R1C2R_1C_2 would intersect HH, contrary to our assumption.

Now, without loss of generality assume that V(C1R2)∩V(H)≠∅V(C_1R_2)\cap V(H)\ne\varnothing. Let T∗T^* be the subtrail of C−xC-x obtained from concatenating the ears T1,…,Tn−1T_1,\ldots,T_{n-1} in the appropriate order. Note that, since n≥2n\ge2, T∗T^* is non-empty. Additionally, v∉V(T∗)v\notin V(T^*) by our assumptions, implying in particular that T∗T^* is either a subtrail of C1−xC_1-x, or a subtrail of C2−xC_2-x. Moreover, V(T∗)∩V(H)≠∅V(T^*)\cap V(H)\ne\varnothing while V(R1C2)∩V(H)=∅V(R_1C_2)\cap V(H)=\varnothing, implying that T∗T^* is in fact a subtrail of C1−xC_1-x, and so in particular a subtrail of C1R2−xC_1R_2-x. As such, H,T1,…,Tn−1H,T_1,\ldots,T_{n-1} is a valid ear decomposition of HH into C1R2C_1R_2. Let ww be the endpoint of Tn2T_n^2 other than vv. By the definition of an ear, w∈V(H)∪V(T∗)w\in V(H)\cup V(T^*). Since w∈V(C2)w\in V(C_2) and V(C2)∩V(H)=∅V(C_2)\cap V(H)=\varnothing, we have w∈V(T∗)w\in V(T^*). Given that every ear decomposition can be trivially extended to a maximal ear decomposition, it follows that the xx-circuit R1C2∈C~R_1C_2\in\widetilde{\mathcal{C}} witnesses that the rank of HH in C~\widetilde{C} is at most n−1n-1. In particular, the rank of C~\widetilde{C} is strictly smaller than that of CC, a contradiction completing the proof of the claim. ■\blacksquare

Let qq be the number of circuits of the packing with label not in Γ′\Gamma', and let rr be the number of unused components. The claims imply 2r≤q2r\le q. Choose for each unused component one incident circuit; these rr chosen circuits are distinct and all have labels not in Γ′\Gamma'. Insert an Euler tour of each unused component into its assigned circuit. Concatenate the resulting rr circuits and all circuits of the original packing labeled in Γ′\Gamma', at xx, to form a single circuit DD, provided the collection is non-empty. The other q−rq-r circuits together with DD cover every edge of GG. If DD is absent, the unchanged circuits already form the required decomposition. If DD is present and γ(D)\gamma(D) is not in Γ′\Gamma', keep the circuit DD. Otherwise concatenate DD at xx with one of the q−rq-r unchanged circuits; the resulting circuit has label not in Γ′\Gamma'. In every case, the resulting decomposition has at least q−r≥⌈q/2⌉≥⌈k/2⌉q-r\ge\lceil q/2\rceil\ge\lceil k/2\rceil circuits. □\square

Making an immersion near-full

We first discuss the “universal” group-labeled graphs which we look for as (near-full) immersions.

For positive integers kk and nn, we define the (k,n)(k,n)-flower to be the graph on n+1n+1 vertices x,y1,…,ynx,y_1,\ldots,y_n so that for each i∈[n]i\in[n], there are kk parallel edges between xx and yiy_i. We call xx the center vertex of the flower. If ϕ\phi is an immersion of a flower into a graph GG, then we call the branch vertex of ϕ\phi corresponding to the center of the flower the branch center. A petal is a subgraph of the flower consisting of xx, some yiy_i, and the kk parallel edges between them. Note that if HH is a graph on nn vertices where each vertex has degree at most kk, then the (k,n)(k,n)-flower admits HH as an immersion; we map V(H)V(H) to {y1,y2,…,yn}\{y_1,y_2,\ldots,y_n\}, and then we greedily map E(H)E(H) to two-edge walks of the flower.

Let Γ\Gamma be a finite group. The (Γ,k,n)(\Gamma,k,n)-rich flower is the Γ\Gamma-labeled graph where the graph is the (∣Γ∣k,n)(|\Gamma|k,n)-flower and, for all i∈[n]i\in[n] and α∈Γ\alpha\in\Gamma, there exist kk oriented edges from xx to yiy_i with label α\alpha. Note that if (H,γH)(H,\gamma_H) is a Γ\Gamma-labeled graph on nn vertices where each vertex has degree at most kk, then the (Γ,k,n)(\Gamma,k,n)-rich flower admits (H,γH)(H,\gamma_H) as an immersion. To see this, first map V(H)V(H) to {y1,y2,…,yn}\{y_1,y_2,\ldots,y_n\} as before. Then select one arbitrary orientation e⃗\vec{e} of each edge ee of HH, and map e⃗\vec{e} to a two-edge trail which begins with an edge labeled by the identity and oriented towards the center, and ends with a γH(e⃗)\gamma_H(\vec{e})-labeled edge oriented away from the center.

The goal of this section is to prove the following theorem which essentially allows us to reduce the question of finding large rich flowers as near-full immersions in 4-edge-connected Eulerian group-labeled graphs to finding (even larger) rich flowers as immersions.

Theorem 3.1. Let Γ\Gamma be a finite group and kk and nn be positive integers. Let k′k' and n′n' be integers such that k′≥k∣Γ∣4+log⁡2∣Γ∣+1k' \ge k|\Gamma|^{4+\log_2|\Gamma|}+1 and n′≥n∣Γ∣n' \ge n|\Gamma|. Suppose (G,γ)(G,\gamma) is a 4-edge-connected Eulerian Γ\Gamma-labeled graph such that there exists an immersion ϕ′\phi' of a (Γ,k′,n′)(\Gamma,k',n')-rich flower with center x′x' in (G,γ)(G,\gamma). Then there exists an xx-near-full immersion ϕ\phi of a (Γ,k,n)(\Gamma,k,n)-rich flower with center xx in (G,γ)(G,\gamma). Moreover, if XX and X′X' are the sets of branch vertices of ϕ\phi and ϕ′\phi', respectively, then X⊆X′X\subseteq X', and, specifically, ϕ′(x′)=ϕ(x)\phi'(x')=\phi(x).

The main technical difficulty is the following lemma, which is used to “disentangle” an (x,Γ′)(x,\Gamma')-decomposition from a flower immersion.

Lemma 3.2. Fix an integer k≥2k\ge2. Let Γ\Gamma be a finite group, let Γ′\Gamma' be a proper subgroup of Γ\Gamma, and let (G,γ)(G,\gamma) be a 4-edge-connected Eulerian Γ\Gamma-labeled graph. Suppose that (G,γ)(G,\gamma) contains an xx-near-full immersion ϕ\phi of a Γ′\Gamma'-labeled Eulerian graph (H,γH)(H,\gamma_H) where HH has every edge incident to a single vertex xx. Let γG′\gamma'_G be an accommodating labeling of the immersion. Furthermore, suppose that (G,γG′)(G,\gamma'_G) contains an (ϕ(x),Γ′)(\phi(x),\Gamma')-decomposition of size at least kk. Then (G,γ)(G,\gamma) has an xx-near-full immersion of a graph obtained from (H,γH)(H,\gamma_H) by deleting at most 2k+22k+2 edges and adding kk loops at xx with label outside Γ′\Gamma'.

Proof. For the duration of the proof, labels refer to the fixed shifting γG′\gamma'_G of γ\gamma. We first extend the xx-near-full immersion φ\varphi to a full immersion of the graph obtained from (H,γH)(H,\gamma_H) by possibly adding a single loop e^\hat{e} at xx with the appropriate γG′\gamma'_G-label (if the xx-near-full is in fact a full immersion, then we do not add e^\hat{e}). For notational convenience we will assume x=φ(x)x=\varphi(x). We partition E(G)E(G) into circuits C={C1,…,Cℓ}\mathcal{C}=\{C_1,\ldots,C_\ell\} each beginning and ending at xx such that

  1. at least kk of them have label outside Γ′\Gamma', and

  2. the size of the symmetric difference of transitions of φ\varphi and transitions of C\mathcal{C} is minimized.

We note that we minimize transitions with respect to φ\varphi only after extending it to a full immersion. Some choice of C\mathcal{C} exists because (G,γG′)(G,\gamma'_G) contains an (x,Γ′)(x,\Gamma')-decomposition of size at least kk. Order the circuits such that C1,…,CmC_1,\ldots,C_m have label outside Γ′\Gamma', and Cm+1,…,CℓC_{m+1},\ldots,C_\ell have label in Γ′\Gamma' for some m≥km\geq k. We partition E(G)E(G) into E1=⋃i=1mE(Ci)E_1=\bigcup_{i=1}^{m}E(C_i) and E2=⋃i=m+1ℓE(Ci)E_2=\bigcup_{i=m+1}^{\ell}E(C_i).

We claim that for any branch trail TT of φ\varphi, either every edge of TT is contained in E1E_1 or every edge of TT is contained in E2E_2. Suppose otherwise, and let e⃗,f⃗\vec{e},\vec{f} be a pair of edges in TT such that (e⃗,f⃗)(\vec{e},\vec{f}) is a transition of TT and ee is in a circuit CiC_i, ff is in a circuit CjC_j, and exactly one of i,ji,j is in [m][m]. By possibly reversing the orientation of TT we may assume i∈[m]i\in[m] and j∈[ℓ]∖[m]j\in[\ell]\setminus[m], and similarly we may orient Ci,CjC_i,C_j such that e⃗\vec{e} is in CiC_i and f⃗\vec{f} is in CjC_j. Let Ci=Ci1Ci2C_i=C_i^1C_i^2 such that e⃗\vec{e} is the last edge of Ci1C_i^1, and let Cj=Cj1Cj2C_j=C_j^1C_j^2 such that f⃗\vec{f} is the first edge of Cj2C_j^2, where possibly Ci2C_i^2 or Cj1C_j^1 is empty. If both are empty, consider removing CiC_i and CjC_j from C\mathcal{C} and adding Cj′=CiCjC'_j=C_iC_j. This circuit has label γG′(Ci)γG′(Cj)∉Γ′\gamma'_G(C_i)\gamma'_G(C_j)\notin\Gamma', so the same number of circuits in the new collection are labeled outside Γ′\Gamma'. Furthermore this adds the transition (e⃗,f⃗)(\vec{e},\vec{f}) to the collection, contradicting the choice of C\mathcal{C}.

Hence we may assume one of Ci2,Cj1C_i^2,C_j^1 is nonempty. Consider replacing Ci,CjC_i,C_j in C\mathcal{C} by the circuits Ci1Cj2,Cj1Ci2C_i^1C_j^2,C_j^1C_i^2. Note that this adds the transition (e⃗,f⃗)(\vec{e},\vec{f}) to the collection while only removing transitions which do not appear in φ\varphi. Thus Ci1Cj2,Cj1Ci2C_i^1C_j^2,C_j^1C_i^2 is a better choice of circuits unless γG′(Ci1Cj2),γG′(Cj1Ci2)∈Γ′\gamma'_G(C_i^1C_j^2),\gamma'_G(C_j^1C_i^2)\in\Gamma'. However because γG′(Cj)∈Γ′\gamma'_G(C_j)\in\Gamma' this would imply

γG′(Ci)=γG′(Ci1)γG′(Ci2)=γG′(Ci1)γG′(Cj2)γG′(Cj2)−1γG′(Cj1)−1γG′(Cj1)γG′(Ci2)=γG′(Ci1Cj2)γG′(Cj)−1γG′(Cj1Ci2)∈Γ′,\begin{aligned} \gamma'_G(C_i)&=\gamma'_G(C_i^1)\gamma'_G(C_i^2)\\ &=\gamma'_G(C_i^1)\gamma'_G(C_j^2)\gamma'_G(C_j^2)^{-1}\gamma'_G(C_j^1)^{-1}\gamma'_G(C_j^1)\gamma'_G(C_i^2)\\ &=\gamma'_G(C_i^1C_j^2)\gamma'_G(C_j)^{-1}\gamma'_G(C_j^1C_i^2)\\ &\in\Gamma', \end{aligned}

a contradiction. This completes the proof that every trail of φ\varphi has all edges entirely contained in one of E1,E2E_1,E_2.

We now claim that there are at most k+1k+1 circuits with label outside Γ′\Gamma' in C\mathcal{C}, that is, m≤k+1m\leq k+1. Suppose for a contradiction that m≥k+2m\geq k+2. First, we observe that every branch trail of φ\varphi has all its edges in a single circuit of C\mathcal{C}. If not, some branch trail has a transition (e⃗,f⃗)(\vec{e},\vec{f}) whose edges belong to distinct circuits CiC_i and CjC_j. Reconnecting these circuits as above adds this transition and removes only transitions not belonging to φ\varphi. The resulting collection still contains at least m−2≥km-2\ge k circuits with label outside Γ′\Gamma', contradicting the choice of C\mathcal{C}.

Choose a circuit CiC_i with label outside Γ′\Gamma' which does not contain any edge of φ(e^)\varphi(\hat{e}), if e^\hat{e} is defined. Let JJ be the subgraph of HH consisting of the edges whose branch trails have their edges in CiC_i. Since the extended immersion is full, these branch trails partition E(Ci)E(C_i). By construction, every vertex of JJ has even degree. Moreover, every edge of JJ is incident with xx, so we conclude that JJ is connected and has an Eulerian tour beginning and ending at xx.

Following this Eulerian tour through the corresponding branch trails gives a circuit DD beginning and ending at xx with E(D)=E(Ci)E(D)=E(C_i) but possibly changing the order and orientation of the edges of CiC_i. Every edge of JJ has label in Γ′\Gamma', and hence γG′(D)∈Γ′\gamma'_G(D)\in\Gamma'. Furthermore, DD contains every transition of φ\varphi on these edges. The circuit CiC_i must omit at least one such transition, as otherwise it would itself be a concatenation of complete branch trails, possibly reversed, and would therefore have label in Γ′\Gamma', which is not the case. Since CiC_i and DD have the same number of transitions, it follows that replacing CiC_i by DD strictly decreases the symmetric difference with the transitions of φ\varphi. This replacement leaves m−1≥km-1\ge k circuits with label outside Γ′\Gamma', again contradicting the choice of C\mathcal{C}. We conclude that m≤k+1m\le k+1.

Hence there are at most k+1k+1 circuits in C\mathcal{C} with label outside Γ′\Gamma'. Let H′H' be the subgraph of HH which includes only edges whose corresponding trails are contained in E2E_2. We claim that H′H' is formed from HH by deleting at most 2k+22k+2 edges. Let E′E' be the set of edges incident to xx, including loops, which appear as the first or last edge of a branch trail of φ\varphi beginning or ending at xx, respectively. We will show that for any circuit CiC_i with i∈[m]i\in[m], CiC_i contains at most two edges in E′E'. This implies the claim as follows. Note that as every edge in HH is incident to xx, every branch trail of HH contains some edge in E′E'. Then an edge ee is in E(H)∖E(H′)E(H)\setminus E(H') if and only if φ(e)\varphi(e) contains an edge of E1∩E′E_1\cap E'. Thus ∣E(H)∖E(H′)∣≤∣E1∩E′∣≤2m≤2k+2|E(H)\setminus E(H')|\le|E_1\cap E'|\le2m\le2k+2, proving the claim.

Suppose to reach a contradiction that a circuit CiC_i for i∈[m]i\in[m] contains at least three edges in E′E'. Choose one of these edges which is neither the first nor the last edge of CiC_i, and consider its end at xx where its branch trail begins or ends. This end occurs at an internal visit of CiC_i to xx, giving a transition (e⃗,f⃗)(\vec{e},\vec{f}) with the head of e⃗\vec{e} and the tail of f⃗\vec{f} equal to xx. Since the chosen end is an end of a branch trail, this transition does not belong to φ\varphi. Let Ci=Ci1Ci2C_i=C_i^1C_i^2 where the last edge of Ci1C_i^1 is e⃗\vec{e} and the first edge of Ci2C_i^2 is f⃗\vec{f}. Note that γG′(Ci)=γG′(Ci1)γG′(Ci2)\gamma'_G(C_i)=\gamma'_G(C_i^1)\gamma'_G(C_i^2), so one of these circuits has label outside Γ′\Gamma'. Then we can modify C\mathcal{C} by replacing CiC_i with the two circuits Ci1,Ci2C_i^1,C_i^2 to contradict the choice of C\mathcal{C} to minimize the symmetric difference with the transitions of φ\varphi.

We then find the desired xx-near-full immersion as follows. On E1E_1 we take the circuits C1,…,CkC_1,\ldots,C_k as immersions of loops, and on E2E_2 we take φ\varphi restricted to H′H'.

This accounts for all edges except possibly edges of Ck+1C_{k+1} if m=k+1m=k+1 and edges of φ(e^)\varphi(\hat{e}) if it exists and its branch trail lies in E2E_2. Each such subset of edges, if it is nonempty, forms a circuit through xx, and we conclude that the xx-near-full immersion exists as claimed, completing the proof. □

The near-full conclusion in the statement of the lemma is necessary in general. Already for Γ=Z2\Gamma=\mathbb{Z}_2 and Γ′={0}\Gamma'=\{0\}, the total label of GG determines the parity of mm, and may force m=k+1m=k+1 rather than m=km=k.

We need one more type of flower in order to build up to rich flowers. We say that a Γ\Gamma-labeled graph is a (Γ,k,n)(\Gamma,k,n)-generating flower if there exists a generating set SS for Γ\Gamma so that 1∈S1\in S, the graph is an (∣S∣k,n)(|S|k,n)-flower, and for all i∈[n]i\in[n] and α∈S\alpha\in S, there exist kk oriented edges from xx to yiy_i with label α\alpha. We call SS the generator.

Our main strategy will be to start with a flower with every edge labeled by the identity, and grow generating flowers for larger and larger subgroups until we have a rich flower. Hence we need the following two lemmas, which give the starting and ending point of the process.

The first is a Ramsey-type lemma for flowers in group-labeled graphs.

Lemma 3.3 ([11]). Let Γ\Gamma be a finite group, let kk and nn be positive integers, and let (G,γ)(G,\gamma) be a Γ\Gamma-labeled graph so that GG is a (k∣Γ∣,n)(k|\Gamma|,n)-flower with center xx. Then there is an xx-near-full immersion of the ({1},k,n)(\{1\},k,n)-rich flower with center xx into (G,γ)(G,\gamma) and the peripheral branch vertices are precisely the peripheral vertices of GG.

The second lemma shows that for large enough kk, every (Γ,k,n)(\Gamma,k,n)-generating flower is “universal”.

Lemma 3.4 ([11]). Let Γ\Gamma be a finite group and kk and nn be positive integers. Then any (Γ,k∣Γ∣2,n)(\Gamma,k|\Gamma|^2,n)-generating flower GG with center xx admits an xx-near-full immersion of the (Γ,k,n)(\Gamma,k,n)-rich flower with center xx mapping its peripheral branch vertices bijectively to the peripheral vertices of GG.

The above lemmas, as originally stated in [11] as lemmas 4.2 and 4.1, respectively, do not specify the branch vertices beyond the center vertex of the star and do not specify that the immersion is xx-nearly full. The stronger statements above follow immediately from the proofs in [11] and we omit the derivation here.

We are now ready to prove the main result which we repeat here for convenience.

Theorem 3.1. Let Γ\Gamma be a finite group and kk and nn be positive integers. Let k′k' and n′n' be integers such that k′≥k∣Γ∣4+log⁡2∣Γ∣+1k'\ge k|\Gamma|^{4+\log_2|\Gamma|}+1 and n′≥n∣Γ∣n'\ge n|\Gamma|. Suppose (G,γ)(G,\gamma) is a 4-edge-connected Eulerian Γ\Gamma-labeled graph such that there exists an immersion φ′\varphi' of a (Γ,k′,n′)(\Gamma,k',n')-rich flower with center x′x' in (G,γ)(G,\gamma). Then there exists an xx-near-full immersion φ\varphi of a (Γ,k,n)(\Gamma,k,n)-rich flower with center xx in (G,γ)(G,\gamma). Moreover, if XX and X′X' are the sets of branch vertices of φ\varphi and φ′\varphi', respectively, then X⊆X′X\subseteq X' and, specifically, φ′(x′)=φ(x)\varphi'(x')=\varphi(x).

Proof. By possibly decreasing k′k' by one, we assume k′k' is even with k′≥k∣Γ∣4+log⁡2∣Γ∣k' \ge k|\Gamma|^{4+\log_2|\Gamma|}. Let xx be the branch center of the (Γ,k′,n′)(\Gamma,k',n')-rich flower immersion. Consider arbitrarily extending this to a full immersion, so (G,γ)(G,\gamma) has a full immersion of the (∣Γ∣k′,n′)(|\Gamma|k',n')-flower with branch center xx and arbitrary labels. By Lemma 3.3, this immerses the ({1},k′,n′)(\{1\},k',n')-rich flower with branch center xx. Because every edge of the rich flower is incident to xx, this is in fact an xx-near-full immersion.

Thus by Observation 1.1, (G,γ)(G,\gamma) has an xx-near-full immersion of the ({1},k′,n′)(\{1\},k',n')-rich flower with branch center xx. Note also that for any proper subgroup Γ′\Gamma' of Γ\Gamma, and any shifting γ~\widetilde{\gamma} of γ\gamma, (G,γ~)(G,\widetilde{\gamma}) has an (x,Γ′)(x,\Gamma')-packing of size k′n′k'n'. This holds because the original rich flower has such a packing for every proper subgroup, and shifting simultaneously conjugates the labels of all circuits based at xx.

We now find a (Γ′,k^,n^)(\Gamma',\widehat{k},\widehat{n})-generating flower as an xx-near-full immersion φ\varphi in (G,γ)(G,\gamma) whose branch vertices belong to X′X' and whose center maps to x=φ(x′)x=\varphi(x'), such that

  1. Γ′\Gamma' is a subgroup of Γ\Gamma,

  1. k^\widehat{k} is even with k∣Γ∣2⋅(4∣Γ∣)log⁡2(∣Γ∣/∣Γ′∣)≤k^≤k′k|\Gamma|^2\cdot(4|\Gamma|)^{\log_2(|\Gamma|/|\Gamma'|)}\le\widehat{k}\le k',

  1. n∣Γ∣∣Γ′∣≤n^≤n′n\frac{|\Gamma|}{|\Gamma'|}\le\widehat{n}\le n', and

  1. subject to the above, ∣Γ′∣|\Gamma'| is as large as possible.

Note that some choice exists by taking the ({1},k′,n′)(\{1\},k',n')-rich flower. We now claim that such a choice must have Γ′=Γ\Gamma'=\Gamma. If this holds, then we have a (Γ,k∣Γ∣2,n)(\Gamma,k|\Gamma|^2,n)-generating flower as an xx-near-full immersion. We then apply Lemma 3.4 and Observation 1.1 to obtain a (Γ,k,n)(\Gamma,k,n)-rich flower as an xx-near-full immersion in (G,γ)(G,\gamma), with branch vertices contained in X′X' and branch center φ(x′)\varphi(x'), as required.

Suppose to reach a contradiction that φ\varphi is an xx-near-full immersion of a (Γ′,k^,n^)(\Gamma',\widehat{k},\widehat{n})-generating flower (H,γH)(H,\gamma_H) for Γ′\Gamma' a proper subgroup of Γ\Gamma. Note that because k^\widehat{k} is even, HH is Eulerian. Let k∗k^* be an even integer such that k^4∣Γ∣≤k∗≤k^−22∣Γ∣\frac{\widehat{k}}{4|\Gamma|}\le k^*\le\frac{\widehat{k}-2}{2|\Gamma|}, and let n∗=⌊n^/2⌋n^*=\lfloor\widehat{n}/2\rfloor. Note that because k≥1k\ge1 and ∣Γ∣≥∣Γ∣/∣Γ′∣≥2|\Gamma|\ge|\Gamma|/|\Gamma'|\ge2, we have k^≥4∣Γ∣3≥8∣Γ∣+4\widehat{k}\ge4|\Gamma|^3\ge8|\Gamma|+4. Hence k^−22∣Γ∣≥k^4∣Γ∣+2\frac{\widehat{k}-2}{2|\Gamma|}\ge\frac{\widehat{k}}{4|\Gamma|}+2, so such a choice of k∗k^* exists.

Let γG′\gamma'_G be an accommodating labeling for φ\varphi. By the preceding observation, (G,γG′)(G,\gamma'_G) contains an (x,Γ′)(x,\Gamma')-packing of size k′n′≥k^n^≥2(∣Γ∣−1)k∗n∗k'n'\ge\widehat{k}\widehat{n}\ge2(|\Gamma|-1)k^*n^*. By Theorem 2.1, (G,γG′)(G,\gamma'_G) therefore contains an (x,Γ′)(x,\Gamma')-decomposition of size at least (∣Γ∣−1)k∗n∗(|\Gamma|-1)k^*n^*. By Lemma 3.2, (G,γ)(G,\gamma) contains an xx-near-full immersion of a graph obtained from (H,γH)(H,\gamma_H) by deleting at most 2(∣Γ∣−1)k∗n∗+22(|\Gamma|-1)k^*n^*+2 edges and adding (∣Γ∣−1)k∗n∗(|\Gamma|-1)k^*n^* loops at xx with label outside Γ′\Gamma'. We then delete the n∗n^* petals which had the most edges deleted. If n^\widehat{n} is odd, we discard one additional petal so that exactly n∗n^* petals remain. Each remaining petal had at most 2(∣Γ∣−1)k∗+22(|\Gamma|-1)k^*+2 edges deleted. By possibly ignoring some branch trails of the immersion (and utilizing Observation 1.1), we see that (G,γ)(G,\gamma) has an xx-near-full immersion of the graph obtained from the (Γ′,2k∗,n∗)(\Gamma',2k^*,n^*)-generating flower by adding (∣Γ∣−1)k∗n∗(|\Gamma|-1)k^*n^* loops at xx with label outside Γ′\Gamma'. We then take k∗n∗k^*n^* of these loops which have the same label α∈Γ∖Γ′\alpha\in\Gamma\setminus\Gamma'. Let Γ′′\Gamma'' be the subgroup generated by Γ′∪{α}\Gamma' \cup\{\alpha\}. By sacrificing k∗k^* trails with identity label on each petal, we obtain an xx-near-full immersion of the (Γ′′,k∗,n∗)(\Gamma'', k^*, n^*)-generating flower with branch center xx. Because Γ′\Gamma' is a proper subgroup of Γ′′\Gamma'', ∣Γ′′∣/∣Γ′∣|\Gamma''|/|\Gamma'| is an integer, and hence at least 2. Thus

k∗≥k^4∣Γ∣≥k∣Γ∣2⋅(4∣Γ∣)log⁡2(∣Γ∣/∣Γ′∣)−1≥k∣Γ∣2⋅(4∣Γ∣)log⁡2(∣Γ∣/∣Γ′′∣)k^* \ge\frac{\widehat{k}}{4|\Gamma|} \ge k|\Gamma|^2 \cdot(4|\Gamma|)^{\log_2(|\Gamma|/|\Gamma'|)-1} \ge k|\Gamma|^2 \cdot(4|\Gamma|)^{\log_2(|\Gamma|/|\Gamma''|)}
n∗=⌊n^2⌋≥⌊∣Γ∣∣Γ′∣n2⌋≥⌊2∣Γ∣∣Γ′′∣n2⌋=∣Γ∣∣Γ′′∣n.n^* = \left\lfloor\frac{\widehat{n}}{2} \right\rfloor\ge\left\lfloor\frac{|\Gamma|}{|\Gamma'|}\frac{n}{2} \right\rfloor\ge\left\lfloor\frac{2|\Gamma|}{|\Gamma''|}\frac{n}{2} \right\rfloor= \frac{|\Gamma|}{|\Gamma''|}n.

Therefore this immersion contradicts the choice of φ\varphi.

Theorem 1.2, which we restate for convenience, now follows easily.

Theorem 1.2. Let Γ\Gamma be a finite group. For every Γ\Gamma-labeled graph (H,γH)(H,\gamma_H) there exists a Γ\Gamma-labeled graph (H′,γH′)(H',\gamma_{H'}) such that for every Eulerian 4-edge-connected Γ\Gamma-labeled graph (G,γG)(G,\gamma_G) and for every vertex x∈V(H)x \in V(H), if (G,γG)(G,\gamma_G) contains (H′,γH′)(H',\gamma_{H'}) as an immersion, then (G,γG)(G,\gamma_G) contains (H,γH)(H,\gamma_H) as an xx-near-full immersion.

Proof. Fix a vertex x∈V(H)x \in V(H). Let k=2∣E(H)∣+2k = 2|E(H)| + 2 and n=∣V(H)∣n = |V(H)|. Let (F,γF)(F,\gamma_F) be the (Γ,k,n)(\Gamma,k,n)-rich flower.

There is an immersion ψ\psi of (H,γH)(H,\gamma_H) into (F,γF)(F,\gamma_F) mapping xx to the center of FF such that every unused edge of FF is incident with its center, making ψ\psi an xx-near-full immersion.

Choose k′k' and n′n' satisfying the bounds in Theorem 3.1, and let (H′,γH′)(H',\gamma_{H'}) be the (Γ,k′,n′)(\Gamma,k',n')-rich flower. We claim (H′,γH′)(H',\gamma_{H'}) is the desired Γ\Gamma-labeled graph. Suppose that (G,γ)(G,\gamma) is Eulerian and 4-edge-connected and contains (H′,γH′)(H',\gamma_{H'}) as an immersion. By Theorem 3.1, (G,γ)(G,\gamma) contains (F,γF)(F,\gamma_F) as a near-full immersion at its center. Composing this immersion with ψ\psi and applying Observation 1.1 gives an xx-near-full immersion of (H,γH)(H,\gamma_H) in (G,γ)(G,\gamma), as required.

Extending a near-full immersion

In this section we discuss under what conditions the near-full immersion in Theorem 1.2 can be replaced by a full immersion. This cannot always be the case: suppose that (G,γG)(G,\gamma_G) and (H,γH)(H,\gamma_H) are Eulerian graphs labeled over Z2k\mathbb{Z}_2^k for some kk such that the sum of all edge weights in GG is different from the sum of all edge weights in HH (note that orientation doesn’t matter because every element is its own inverse and the group is abelian, so this sum is well defined). Moreover, the sum is invariant under shifting: shifting at a vertex changes the total by the vertex’s degree times the shifting element, which is always zero because the graph is Eulerian. Then it cannot be that (G,γG)(G,\gamma_G) contains (H,γH)(H,\gamma_H) as a full immersion, even though (G,γG)(G,\gamma_G) can contain arbitrary group labeled immersions. It turns out that this is in some sense the only restriction.

We first need some notions from group theory. The commutator subgroup of a group Γ\Gamma, denoted [Γ,Γ][\Gamma,\Gamma], is the subgroup generated by all the commutators, that is, all elements of the form a−1b−1aba^{-1}b^{-1}ab for a,b∈Γa,b\in\Gamma. It is well known that [Γ,Γ][\Gamma,\Gamma] is a normal subgroup and that Γ/[Γ,Γ]\Gamma/[\Gamma,\Gamma] is abelian; in fact, for any normal subgroup NN of Γ\Gamma, Γ/N\Gamma/N is abelian if and only if NN contains the commutator subgroup. We denote by Γ2\Gamma^2 the set {a2:a∈Γ}\{a^2:a\in\Gamma\}. We note that Γ2[Γ,Γ]={ab:a∈Γ2,b∈[Γ,Γ]}\Gamma^2[\Gamma,\Gamma]=\{ab:a\in\Gamma^2,b\in[\Gamma,\Gamma]\} is a subgroup of Γ\Gamma. To see this, modulo [Γ,Γ][\Gamma,\Gamma] the group is abelian, so the product of two squares is a square and the inverse of a square is a square, implying Γ2[Γ,Γ]\Gamma^2[\Gamma,\Gamma] is a subgroup. Since it contains [Γ,Γ][\Gamma,\Gamma], it is normal as well. Finally, we note that if Γ\Gamma is a finite group then Γ/(Γ2[Γ,Γ])\Gamma/(\Gamma^2[\Gamma,\Gamma]) is isomorphic to Z2k\mathbb{Z}_2^k for some k≥0k\ge0; the group is abelian and every element squares to the identity.

Theorem 4.1. Let Γ\Gamma be a finite group. For every Eulerian Γ\Gamma-labeled graph (H,γH)(H,\gamma_H) with at least one edge there exists a Γ\Gamma-labeled graph (H′,γH′)(H',\gamma_{H'}) such that for any 4-edge-connected Eulerian Γ\Gamma-labeled graph (G,γG)(G,\gamma_G) with no (H,γH)(H,\gamma_H) full immersion, one of the following holds.

  1. There exists a normal subgroup Γ′\Gamma' of Γ\Gamma such that Γ/Γ′\Gamma/\Gamma' is isomorphic to Z2k\mathbb{Z}_2^k for some kk, and over this quotient labeling the sum of the edge labels in (G,γG)(G,\gamma_G) is different than that of (H,γH)(H,\gamma_H).

  1. (G,γG)(G,\gamma_G) does not contain (H′,γH′)(H',\gamma_{H'}) as an immersion.

We note as before that in the first option, the sum over the labeling of all edges of (G,γG)(G,\gamma_G) is well defined because the quotient group is isomorphic to Z2k\mathbb{Z}_2^k. Since GG is Eulerian, this sum is also invariant under shifting. In fact, in option 1 we may take Γ′=Γ2[Γ,Γ]\Gamma'=\Gamma^2[\Gamma,\Gamma]. It is not hard to see that for any Eulerian Γ\Gamma-labeled graphs (G,γG)(G,\gamma_G) and (H,γH)(H,\gamma_H) such that option 1 holds, (G,γG)(G,\gamma_G) does not contain (H,γH)(H,\gamma_H) as a full immersion.

Proof of Theorem 4.1. Fix an arbitrary vertex x∈V(H)x\in V(H) incident with an edge of HH and consider the Γ\Gamma-labeled graph (H∘,γH∘)(H^\circ,\gamma_{H}^{\circ}) obtained from (H,γH)(H,\gamma_H) by adding 2∣Γ∣2|\Gamma| loops of label aa at xx, for each a∈Γa\in\Gamma. Applying Theorem 1.2 to (H∘,γH∘)(H^\circ,\gamma_{H}^{\circ}) yields a Γ\Gamma-labeled graph (H′,γH′)(H',\gamma_{H'}) such that, if (G,γG)(G,\gamma_G) contains (H′,γH′)(H',\gamma_{H'}) as an immersion, then (G,γG)(G,\gamma_G) contains (H∘,γH∘)(H^\circ,\gamma_{H}^{\circ}) as an xx-near-full immersion. If (G,γG)(G,\gamma_G) does not contain (H′,γH′)(H',\gamma_{H'}) as an immersion we immediately conclude. We may therefore assume that (G,γG)(G,\gamma_G) contains an xx-near-full immersion φ∘\varphi^\circ of (H∘,γH∘)(H^\circ,\gamma_{H}^{\circ}). For simplicity we also assume that x=φ∘(x)x=\varphi^\circ(x). Fix an accommodating labeling γG′\gamma'_G for φ∘\varphi^\circ, and use this labeling for all circuit and trail labels below. Since GG is Eulerian, shifting does not change its total label in any elementary abelian 2-group quotient. Thus if outcome 1 holds for the labeling γG′\gamma'_G it holds as well for the original labeling.

If there are unused edges, let CC be an Eulerian circuit of their unique non-trivial component, starting and ending at xx, and fix α=γG′(C)\alpha=\gamma'_G(C). If there are no unused edges, let α=1\alpha=1 and omit CC from the concatenations below. Assume to reach a contradiction that option 1 does not hold. Our goal is to concatenate CC, if present, with the branch trails of ϕ∘\phi^\circ corresponding to the added loops, in such a way that the product of all the labels is the identity; in this case we are done, as we may discard the branch trails of ϕ∘\phi^\circ corresponding to the added loops, obtaining an xx-near-full immersion ϕ\phi of (H,γH)(H,\gamma_H) in the process, append the discarded branch trails to CC, if present, in a way that gives us a circuit C′C' starting and ending at xx and labeled by the identity, and then append C′C' to any branch trail of ϕ\phi corresponding to an edge of HH incident with xx in order to obtain (H,γH)(H,\gamma_H) as a full immersion.

Indeed, assuming outcome 1 does not hold, it must in particular not hold with respect to Γ2[Γ,Γ]\Gamma^2[\Gamma,\Gamma]. Over this quotient, the sum of the labels of the edges in the branch trails of ϕ\phi equals the total label of (H,γH)(H,\gamma_H), and hence that of (G,γG′)(G,\gamma'_G). Moreover, the total label of the branch trails corresponding to the added loops is the identity, since each label occurs an even number of times. Consequently, the image of α\alpha in Γ/(Γ2[Γ,Γ])\Gamma/(\Gamma^2[\Gamma,\Gamma]) is the identity, and therefore α∈Γ2[Γ,Γ]\alpha\in\Gamma^2[\Gamma,\Gamma].

Let K=Γ2[Γ,Γ]K = \Gamma^2[\Gamma,\Gamma]. The subgroup generated by all squares is normal, and its quotient has every element of order at most two, so that quotient is abelian. Thus this subgroup contains [Γ,Γ][\Gamma,\Gamma], and consequently equals KK. Since the squares generate KK, we may write α−1=a12⋯at2\alpha^{-1} = a_1^2 \cdots a_t^2 for some a1,…,at∈Γa_1,\ldots,a_t \in\Gamma, where t≤∣K∣−1≤∣Γ∣−1t \le|K|-1 \le|\Gamma|-1 because a shortest such expression has distinct partial products. If α=1\alpha= 1, we take t=0t = 0. For each i∈[t]i \in[t], select two previously unused branch trails of ϕ∘\phi^\circ corresponding to added loops of label aia_i, and orient both to have label aia_i under γG′\gamma'_G. There are sufficient copies, since we use at most 2t<2∣Γ∣2t < 2|\Gamma| copies of any label. Concatenating these trails in the specified order gives label α−1\alpha^{-1}. For each label, an even number of its added loops remain unused. Pair these loops, and for each pair traverse one corresponding branch trail in its prescribed orientation and the other in reverse, so that the pair contributes the identity. Concatenate CC, if present, with the selected trails and then these remaining pairs. The resulting circuit begins and ends at xx, contains every residual edge and every edge of the added-loop branch trails exactly once, and has label αα−1=1\alpha\alpha^{-1} = 1, as desired.

We conclude with the proof of Theorem 1.4, which we restate here.

Theorem 1.4. Let Γ\Gamma be a finite group. For every Eulerian Γ\Gamma-labeled graph (H,γH)(H,\gamma_H) with at least one edge, there exists a positive integer t=t(Γ,H)t = t(\Gamma,H) such that the following holds. Let (G,γG)(G,\gamma_G) be a 4-edge-connected Eulerian Γ\Gamma-labeled graph with no (H,γH)(H,\gamma_H) full immersion. Then one of the following holds.

  1. There exists a normal subgroup Γ′\Gamma' of Γ\Gamma such that Γ/Γ′\Gamma/\Gamma' is isomorphic to Z2r\mathbb{Z}_2^r for some nonnegative integer rr, and over this quotient labeling the sum of the edge labels in (G,γG)(G,\gamma_G) differs from that in (H,γH)(H,\gamma_H).

  1. There exist a shifting γ~\widetilde{\gamma} of γG\gamma_G and a tree-cut decomposition (T,B)(T,\mathcal{B}) of GG such that for every bag B∈BB \in\mathcal{B}, at least one of the following holds.

  • (a) There are at most tt vertices in the torso of BB of degree greater than tt, and none of them are the new vertices of the torso.

  • (b) There exists X⊆E(G)X \subseteq E(G) such that (X,γ~)(X,\widetilde{\gamma}) is a certificate for BB of value at most tt.

Proof of Theorem 1.4. Fix Γ\Gamma and (H,γH)(H,\gamma_H), and let (H′,γH′)(H',\gamma_{H'}) be the graph supplied by Theorem 4.1. Let n=∣V(H′)∣n = |V(H')|, and fix a positive integer kk such that every vertex of H′H' is incident to at most kk edges. Let

t=4kn∣Γ∣6+⌊log⁡2∣Γ∣⌋.t = 4kn|\Gamma|^{6+\lfloor\log_2|\Gamma|\rfloor}.

In particular, t≥n∣Γ∣t \ge n|\Gamma|.

Let (G,γG)(G,\gamma_G) be a 4-edge-connected Eulerian Γ\Gamma-labeled graph with no (H,γH)(H,\gamma_H) full immersion. If the first outcome of Theorem 4.1 holds, then the first outcome of Theorem 1.4 holds as well. Thus we may assume that (G,γG)(G,\gamma_G) does not contain (H′,γH′)(H',\gamma_{H'}) as an immersion. Theorem 1.3 gives a shifting γ~\widetilde{\gamma} of γG\gamma_G and a tree-cut decomposition (T,B)(T,\mathcal{B}) of GG satisfying the second outcome of Theorem 1.4, completing the proof. □

Declaration of AI use

ChatGPT-6 Astra was used in proofreading and editing the final manuscript, identifying a number of typos as well as mathematical issues in the proof of Theorem 4.1 and Lemma 3.2.

References

  1. [1]D. I. Bernstein. Generic symmetry-forced infinitesimal rigidity: Translations and rotations. SIAM Journal on Applied Algebra and Geometry, 6(2):190 – 215, 2022.arxiv.org/abs/2003.10529
  2. [2]A. Bouchet. Caractérisation des symboles croisés de genre nul. Comptes Rendus de l’Académie des Sciences de Paris, Séries A-B, 274:A724–A727, 1972.
  3. [3]A. Bouchet. Circle graph obstructions. Journal of Combinatorial Theory, Series B, 60(1):107–144, 1994.DOI
  4. [4]M. DeVos, J. McDonald, B. Mohar, and D. Scheide. A note on forbidding clique immersions. The Electronic Journal of Combinatorics, 20(3):P55, 2013.arxiv.org/abs/1207.2117
  5. [5]J. Geelen, B. Gerards, and G. Whittle. Solving Rota’s conjecture. Notices Amer. Math. Soc., 61(7):736–743, 2014.DOI
  6. [6]J. Geelen, O.-j. Kwon, R. McCarty, and P. Wollan. The grid theorem for vertex-minors. Journal of Combinatorial Theory, Series B, 158:93 – 116, 2023.
  7. [7]A. M. H. Gerards. On Tutte’s characterization of graphic matroids—a graphic proof. J. Graph Theory, 20(3):351–359, 1995.
  8. [8]J. L. Gross. Voltage graphs. Discrete Mathematics, 9(3):239–246, 1974.
  9. [9]J. L. Gross and T. W. Tucker. Generating all graph coverings by permutation voltage assignments. Discrete Mathematics, 18(3):273–283, 1977.DOI
  10. [10]V. E. Kaszanitzky, B. Schulze, and S.-i. Tanigawa. Global rigidity of periodic graphs under fixed-lattice representations. Journal of Combinatorial Theory. Series B, 146:176 – 218, 2021.arxiv.org/abs/1612.01379
  11. [11]R. McCarty, C. McFarland, and P. Wollan. The structure of group-labeled graphs forbidding an immersion. arXiv preprint arXiv:2603.08820, 2026.arxiv.org/abs/2603.08820
  12. [12]C. S. J. A. Nash-Williams. On well-quasi-ordering trees. In M. Fiedler, editor, Theory of Graphs and Its Applications (Proceedings of the Symposium, Smolenice, 1963), pages 83–84, Prague, 1964. Publishing House of the Czechoslovak Academy of Sciences.
  13. [13]P. Nelson and Z. Walsh. The extremal function for excluding geometry minors over prime fields. SIAM J. Discrete Math., 36(3):2100–2120, 2022.DOI
  14. [14]J. Paat, I. Stallknecht, Z. Walsh, and L. Xu. On the column number and forbidden submatrices for Δ-modular matrices. SIAM J. Discrete Math., 38(1):1–18, 2024.arxiv.org/abs/2212.03819
  15. [15]R. C. Read and P. Rosenstiehl. On the Gauss crossing problem. In Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, volume 18 of Colloquia Mathematica Societatis János Bolyai, pages 843–876. North-Holland, Amsterdam–New York, 1978.
  16. [16]N. Robertson and P. Seymour. Graph minors XXIII. Nash-Williams’ immersion conjecture. Journal of Combinatorial Theory, Series B, 100(2):181–205, 2010.
  17. [17]P. Seymour. On Tutte’s characterization of graphic matroids. Ann. Discrete Math., 8:83–90, 1980.DOI
  18. [18]S.-i. Tanigawa. Matroids of gain graphs in applied discrete geometry. Trans. Amer. Math. Soc., 367(12):8597–8641, 2015.arxiv.org/abs/1207.3601
  19. [19]P. Wollan. The structure of graphs not admitting a fixed immersion. Journal of Combinatorial Theory, Series B, 110:47–66, 2015.arxiv.org/abs/1302.3867

Paper details

vlnc:W_3uvehke6
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT-6 Astra

View statement
Looking for related papers…
Contents