betaFeedback

WorksMathematics

Non-induced inherent graphs

Abstract

Concepts of avoidable paths and inherent two-rooted graphs were recently introduced for the case of induced subgraphs. In this paper, we translate this framework to the setting of not necessarily induced (NNI) subgraphs, where the structural constraints, as well as conclusions, are significantly relaxed. We develop a new sufficient condition for inherence, and use it to provide complete characterizations of inherent two-rooted paths and forks. We show that for these families, the obvious necessary condition for inherence from the induced case is sufficient in the NNI setting. To complement these results, we introduce two general methods for proving non-inherence and apply them to demonstrate the non-inherence of several classes of two-rooted trees. Keywords: subgraph, two-rooted graph, two-rooted tree, avoidable two-rooted graph, inherent two-rooted graph

MSC (2020): 05C75, 05C60, 05C38, 05C05.

Introduction

In graph theory, graph properties are often characterized by forbidden or mandatory substructures. These substructures are analyzed in two main ways: as induced subgraphs, which preserve all adjacencies from the parent graph, or as the more flexible not necessarily induced (NNI) subgraphs, which require only a subset of vertices and edges.

The concept of “avoidability,” central to our work, has its roots in the study of chordal graphs. The foundational result is Dirac’s theorem [8], which states that every chordal graph contains a simplicial vertex—a vertex whose neighborhood forms a clique. Recognizing that not all graphs have simplicial vertices, Ohtsuki, Cheung, and Fujisawa introduced in 1976 the concept of an avoidable vertex: one for which every induced path of length two centered at this vertex is part of an induced cycle [13]. They proved that such a vertex exists in every graph. The term ‘avoidable vertex’ was introduced by Beisegel et al. [1]; an alternative term used in the literature is ‘OCF-vertex’ (see, e.g., [3, 4, 12]).

Nearly half a century later, this notion was generalized from vertices to paths. Beisegel et al. [1, 2] defined an avoidable path as an induced path whose every “extension” – adding a new vertex to each endpoint so that the obtained longer path is still induced – is contained in an induced cycle. They conjectured that every graph containing an induced kk-vertex path must also contain an avoidable kk-vertex path and proved the claim for k=2k = 2. The conjecture of Beisegel et al. generalizes not only the aforementioned result of Ohtsuki, Cheung, and Fujisawa [13] but also a result by Chvátal, Rusu, and Sritharan [6] who proved the conjecture for graphs excluding chordless cycle of length at least k+3k + 3. In full generality, the conjecture was proved by Bonamy et al. [5] and later strengthened by Gurvich et al. [9], who showed that every induced path can be transformed into an avoidable one through a series of local transformations called shifts.

A further generalization was provided in [11], which established the framework of inherent two-rooted graphs for the induced case. A two-rooted graph (H,s,t)(H, s, t) consists of a graph HH with two specified vertices ss and tt, called roots.

This framework formalizes the notion of an extension for arbitrary structures: an extension of an induced copy of (H,s,t)(H, s, t) in a larger graph GG is an induced subgraph obtained by adding to the copy of HH a pair of pendant edges incident with the copies of ss and tt, respectively. Such an extension is closable if a path exists in GG between these new pendant vertices, using only vertices outside the closed neighborhood of the original copy. A copy of (H,s,t)(H, s, t) is then defined as avoidable if all of its possible extensions are closable. In particular, a copy is avoidable if it admits no extensions, in which case it is called simplicial. Finally, a two-rooted graph is inherent if any graph containing an induced copy of HH must also contain an avoidable induced copy of (H,s,t)(H, s, t).{^1} Gurvich et al. [11] identified an important necessary condition for a connected two-rooted graph to be inherent (NCI for short).

Definition 1.1. A two-rooted graph (H,s,t)(H, s, t) is said to have NCI property if:

  • either HH is a path with an endpoint ss,

  • or HH is a tree with maximum degree 3 such that 1=dH(s)≤dH(t)≤21 = d_H(s) \le d_H(t) \le2, with dH(t)=1d_H(t) = 1 if and only if s=ts = t.

In particular, a two-rooted graph (H,s,t)(H, s, t) can only have the NCI property if it is a two-rooted tree, that is, HH is a tree. In [11], Theorem 1.8 it was shown that every inherent connected graph has the NCI property. Yet, determining inherence for a specific graph seems to be difficult. So far, the only known connected (induced) inherent graphs are paths rooted in their endpoints (see [5]), and even some small examples, such as the two-edge path with adjacent roots, are not yet settled (see [11]).

Furthermore, it is an open question whether the problem of recognizing if a given two-rooted graph is inherent is decidable.

Our results

Recall that NNI stands for “not necessarily induced”. The present work pivots from the induced to the NNI setting. This transition is a natural and crucial step, as the structural constraints are significantly relaxed, in the sense that a non-induced copy of a graph HH can exist in many more contexts than an induced one; on the other hand, in general, there are more extensions in the NNI setting than in the induced one. We adopt the two-rooted graph framework but redefine the core concepts for NNI subgraphs. Our goal is to determine how this added flexibility impacts the property of inherence and to identify classes of two-rooted graphs that are robust enough to be inherent in this more general setting.

This paper provides the first systematic study of inherence in the NNI setting. Our starting point is the observation that adapting the definitions and the proofs of [11 Section 3] (mutatis mutandis) to the NNI setting shows similar results also in the NNI setting. In particular, the following holds.

Observation 1.2. All connected inherent two-rooted graphs have NCI property.

We develop new proof techniques tailored to the NNI setting and establish several foundational results. Our main contributions are as follows.

A powerful sufficient condition for a copy of (H,s,t)(H, s, t) to be avoidable in a graph GG is that the subgraph induced by the vertices not in the copy is connected. Any extension of such a copy would have its new vertices within this subgraph and would therefore be closable; in particular, the copy is avoidable. It turns out that for certain two-rooted graphs, the mere absence of simplicial copies guarantees the existence of such a copy of HH. Such two-rooted graphs are called complementary connected or simplicial (CCS) graphs. By definition, CCS graphs are inherent. The converse implication is open.

Using the CCS framework, we provide complete characterizations of inherence for all two-rooted paths3 and for all two-rooted trees with at most six vertices.

Paths: We call a path with roots in both endpoints an endpoint-rooted path. Gurvich et al. showed the following result in the NNI setting.

Theorem 1.3 ([9]). Any endpoint-rooted path is inherent.

We show that for two-rooted paths, the necessary condition for inherence (NCI) is also sufficient in the NNI setting.

Theorem 1.4. Every two-rooted path satisfying the NCI property is a CCS graph, and therefore inherent.

Small trees: We completely characterize inherent two-rooted trees with up to 6 vertices. It turns out that, when the underlying tree is a fork, that is, the unique 5-vertex tree with maximum degree 3, inherence is equivalent to the CCS property. Furthermore, apart from paths and forks,4 the only inherent two-rooted tree on at most 6 vertices is T1(2,1,2)T_1(2,1,2), depicted in Figure 8(a) and formally defined in § 1.2.

Figure 8. (a) (s,t,a,b,c,d)(s,t,a,b,c,d) is a copy of T1(2,1,2)T_1(2,1,2); (b) Names of the arcs of T1(2,1,2)T_1(2,1,2)

Theorem 1.5. T1(2,1,2)T_1(2,1,2) is inherent.

As mentioned above, apart from paths and forks, among connected graphs on at most 6 vertices there exists a single inherent one. Indeed, it seems that inherent graphs are very rare. In this regard, we provide additional necessary conditions for inherence. We show that a two-rooted tree cannot be inherent if its bipartition is too unbalanced. Furthermore, we present a path augmentation method to construct confining graphs for several families of two-rooted trees, including combs of type II, rakes, and certain two-rooted leaf-extended trees (see § 1.2 and § 7.2 for definitions), thereby proving their non-inherence in the NNI setting.

Preliminaries

While we mostly work with undirected graphs, we also use arcs for a particular orientation of a given edge. A copy of a graph HH in a graph GG is a subgraph of GG isomorphic to HH. A subgraph embedding of a graph HH in a graph GG is an injection φ:V(H)→V(G)\varphi: V(H) \to V(G) that maps adjacent vertices to adjacent vertices. The path graph on nn vertices is denoted by PnP_n. For other standard graph theory notation we refer the reader to Diestel [7].

A two-rooted graph is a triple (H,s,t)(H,s,t) such that HH is a graph and ss and tt are two (not necessarily distinct) vertices of HH which we call roots. We will denote two-rooted graphs in calligraphic font, such as G,H\mathcal{G}, \mathcal{H}. For convenience and without loss of generality, we always assume for a two-rooted graph (H,s,t)(H,s,t) that dH(s)≤dH(t)d_H(s) \le d_H(t).

In what follows we adapt the definitions of terms from [11] such as copy, extension, avoidability, inherence, and confining graph to the NNI setting. We point out that in the induced setting these notions differ from ours, see Remark 3.2. Given a graph GG and a two-rooted graph (H,s,t)(H,s,t), a copy of (H,s,t)(H,s,t) in GG is any two-rooted graph (⟨H⟩,⟨s⟩,⟨t⟩)(\langle H\rangle,\langle s\rangle,\langle t\rangle) such that ⟨H⟩\langle H\rangle is a subgraph of GG for which there exists an isomorphism of HH to ⟨H⟩\langle H\rangle mapping ss to ⟨s⟩\langle s\rangle and tt to ⟨t⟩\langle t\rangle.

Given a two-rooted graph H=(H,s,t)\mathcal{H}=(H,s,t), the extension graph of H\mathcal{H} is the graph H′H' obtained from HH by adding to it two pendant edges ss′ss' and tt′tt'; the corresponding two-rooted graph H′=(H′,s′,t′)\mathcal{H}'=(H',s',t') is said to be an extension of H\mathcal{H}. Given a graph GG, a two-rooted graph (H,s,t)(H,s,t), and a copy (⟨H⟩,⟨s⟩,⟨t⟩)(\langle H\rangle,\langle s\rangle,\langle t\rangle) of it in GG, an extension of (⟨H⟩,⟨s⟩,⟨t⟩)(\langle H\rangle,\langle s\rangle,\langle t\rangle) in GG is any extension (H′,s′,t′)(H',s',t') of (⟨H⟩,⟨s⟩,⟨t⟩)(\langle H\rangle,\langle s\rangle,\langle t\rangle) such that H′H' is a subgraph of GG. In particular, V(H′)=V(⟨H⟩)∪{s′,t′}V(H') = V(\langle H\rangle) \cup\{s', t'\}, vertices s′s' and t′t' are distinct, the graph obtained from H′H' by deleting s′s' and t′t' is ⟨H⟩\langle H\rangle, and ⟨s⟩\langle s\rangle and ⟨t⟩\langle t\rangle are unique neighbors of s′s' and t′t' in H′H', respectively. Furthermore, we say that an extension (H′,s′,t′)(H',s',t') of (⟨H⟩,⟨s⟩,⟨t⟩)(\langle H\rangle,\langle s\rangle,\langle t\rangle) in GG is closable if there exists an s′,t′s',t'-path in GG having no vertex in common with V(⟨H⟩)V(\langle H\rangle).

Definition 1.6. Let (⟨H⟩,⟨s⟩,⟨t⟩)(\langle H\rangle,\langle s\rangle,\langle t\rangle) be a copy of a two-rooted graph (H,s,t)(H,s,t) in a graph GG. We say that (⟨H⟩,⟨s⟩,⟨t⟩)(\langle H\rangle,\langle s\rangle,\langle t\rangle) is avoidable (in GG) if all extensions of (⟨H⟩,⟨s⟩,⟨t⟩)(\langle H\rangle,\langle s\rangle,\langle t\rangle) in GG are closable.

In particular, a copy (⟨H⟩,⟨s⟩,⟨t⟩)(\langle H\rangle,\langle s\rangle,\langle t\rangle) of (H,s,t)(H,s,t) in GG that has no extensions is trivially avoidable. Such a copy (⟨H⟩,⟨s⟩,⟨t⟩)(\langle H\rangle,\langle s\rangle,\langle t\rangle) will be called simplicial.

Remark 1.7. If HH is a path and ss and tt are its endpoints, the above definitions of an extension of a copy of (H,s,t)(H,s,t) in a graph GG, a closable extension, a simplicial copy, and an avoidable copy coincide with the corresponding definitions from Gurvich et al. [9 Section 1.1] for the case t=ptht = \mathrm{pth}.

Finally, we introduce the core definition of this paper. In fact, this is the definition from [11] adjusted to the NNI setting.

Definition 1.8. A two-rooted graph (H,s,t)(H,s,t) is inherent if every graph GG that contains a copy of HH also contains an avoidable copy of (H,s,t)(H,s,t).

The following concept provides a natural certificate of non-inherence.

Definition 1.9. Given a two-rooted graph (H,s,t)(H,s,t) and a graph GG, we say that GG confines (H,s,t)(H,s,t) (or: is a confining graph for (H,s,t)(H,s,t)) if GG contains a copy of HH but no avoidable copy of (H,s,t)(H,s,t).

In [11] a necessary condition for inherence of two-rooted graphs was introduced, called PE-inherence. The condition remains necessary in the NNI setting. It follows from [11 Observation 3.24 and Proposition 3.26] that a two-rooted tree is PE-inherent if and only if it cannot be confined by a tree.5

Let us recall the definitions of several infinite families of PE-inherent two-rooted trees introduced in [11]. A graph F(l,k,l′)F(l,k,l') consists of a path Pl+k+l′=(a1,…,al+k+l′)P_{l+k+l'} = (a_1,\ldots,a_{l+k+l'}) and kk pending edges added to vertices al+1,…,al+ka_{l+1},\ldots,a_{l+k}.

  • Two-rooted combs of type I are the two-rooted graphs T1(l,k,l′)=(F(l,k,l′),a1,al)T_1(l,k,l') = (F(l,k,l'),a_1,a_l), where l≥1l \ge1 and k,l′≥0k,l' \ge0 (see Figure 2 and Figure 4 for two examples, namely T1(2,1,1)T_1(2,1,1) and T1(1,1,2)T_1(1,1,2), respectively). Note that T1(l,0,l′)T_1(l,0,l') is a two-rooted path and T1(l,0,0)T_1(l,0,0) is an endpoint-rooted path.

Figure 2. (s,t,a,b,c)(s,t,a,b,c) is a copy of the two-rooted fork T1(2,1,1)T_1(2,1,1).

Figure 4. (d,c,a,b,s)(d,c,a,b,s) is a copy of the two-rooted fork T1(1,1,2)T_1(1,1,2).

  • Two-rooted combs of type II are the two-rooted graphs T2(p,q)=(F(p,q,p),a1,ap+q+1)T_2(p,q)=(F(p,q,p),a_1,a_{p+q+1}), p,q≥1p,q\ge1 (see Figure 16 for an example, namely T2(3,3)T_2(3,3)).

Figure 16. Up to automorphism, the graph admits only one copy of T2(3,3)T_2(3,3), which is clearly not avoidable, thus showing that T2(3,3)T_2(3,3) is confined.

  • Two-rooted combs of type III are the two-rooted graphs

    T3(p,q)=(F(p,q,p+1),a1,ap+q+1),T_3(p,q)=(F(p,q,p+1),a_1,a_{p+q+1}),

    p≥1p\ge1 and q≥0q\ge0 (see Figure 3 for an example, namely T3(1,1)T_3(1,1)).

Figure 3. (c,t,a,b,s)(c,t,a,b,s) is a copy of the two-rooted fork T3(1,1)T_3(1,1).

  • For an integer q≥2q\ge2 we denote by T4(q)T_4(q) the two-rooted graph obtained from the two-rooted comb T2(2,q)T_2(2,q) of type II by subdividing each edge of the form aibia_i b_i, i=3,…,q+2i=3,\ldots,q+2. Any two-rooted graph equivalent to T4(q)T_4(q), for some qq, will be referred to as a two-rooted rake (see Figure 17(a) for an example, namely T4(3)T_4(3)).

Figure 17. Up to automorphism, the graph on the left admits only one copy of T4(3)T_4(3), while the graph on the right admits only one copy of T5(4)T_5(4). Clearly, neither of these copies is avoidable, hence, the two-rooted graphs T4(3)T_4(3) and T5(3)T_5(3) are confined.

  • For an integer q≥3q\ge3 we denote by T5(q)T_5(q) the two-rooted graph obtained from the two-rooted comb T2(2,q)T_2(2,q) of type II by subdividing each edge of the form aibia_i b_i, i=3,…,q+2i=3,\ldots,q+2, and adding a pendant edge to each vertex of degree two joining aia_i and bib_i for all i∈{4,…,q+1}i\in\{4,\ldots,q+1\}. Any two-rooted graph equivalent to T5(q)T_5(q), for some qq, will be referred to as a two-rooted split rake (see Figure 17(b) for an example, namely T5(4)T_5(4)).

Structure of the paper

The paper is structured as follows. In § 2 we develop a framework for proving inherence (see Figure 1 for a summary). We present proofs of Theorem 1.4, the results on two-rooted forks, and Theorem 1.5 in § 3 to § 5, respectively, while in § 6 we discuss disconnected inherent graphs. § 7 presents two main techniques for constructing confining graphs, which are used to prove that a two-rooted graph is not inherent. Namely, § 7.1 demonstrates how to use complete bipartite graphs to confine trees with imbalanced color classes, while § 7.2 introduces the so-called path augmentation method. This technique is then used to construct confining graphs for several families, including combs of type II, rakes, and certain two-rooted leaf-extended trees. In § 8 we outline possible future research directions and pose some open questions. In Appendix § 9, we collect the abbreviations of various properties of two-rooted graphs defined in § 2, while in Appendix § 10, we provide the analysis of all non-inherent two-rooted graphs of order at most 6.

Figure 1. Implications between various properties of connected two-rooted graphs. In general, the implications are of Horn-type, that is, several properties imply another.

AI Usage Statement: Artificial Intelligence was not used in any way for this research or writing.

A framework for proving inherence

A simplicial copy of a two-rooted graph is avoidable by definition. So, in the pursuit of inherent graphs we restrict our attention to graphs that contain copies of a two-rooted graph but all copies are non-simplicial. Also, we are mainly interested in connected two-rooted graphs. Thus we proceed by defining several concepts that capture these properties, and describe relations between them.

Definition 2.1. Let H=(H,s,t)\mathcal{H}=(H,s,t) be a two-rooted graph. A graph GG is H\mathcal{H}-smooth if GG is connected, GG contains a copy of HH, and there are no simplicial copies of H\mathcal{H} in GG.

Due to Observation 1.2 we are mainly concerned in H\mathcal{H}-smooth graphs for the case when H\mathcal{H} has the NCI property.

In many cases H\mathcal{H}-smoothness implies that there are many copies of H\mathcal{H}. We introduce several concepts capturing this ‘richness’ of copies of a two-rooted graph. Recall that a subgraph embedding of a graph HH in a graph GG is an injection φ:V(H)→V(G)\varphi: V(H) \to V(G) that maps adjacent vertices to adjacent vertices.

Definition 2.2. A two-rooted graph H=(H,s,t)\mathcal{H}=(H,s,t) is said to be

  • VU (Vertex Universal) if for any H\mathcal{H}-smooth graph G=(V,E)G=(V,E), any v∈Vv \in V, and any x∈V(H)x \in V(H), there exists a subgraph embedding φ\varphi of HH in GG such that φ(x)=v\varphi(x)=v;

  • WVU (Weakly Vertex Universal) if for any H\mathcal{H}-smooth graph G=(V,E)G=(V,E), any v∈Vv \in V contained in a copy of HH in GG, and any x∈V(H)x \in V(H), there exists a subgraph embedding φ\varphi of HH in GG such that φ(x)=v\varphi(x)=v;

  • AU (Arc Universal) if for any H\mathcal{H}-smooth graph G=(V,E)G=(V,E), any arc (u,v)∈E(u,v) \in E, and any arc (x,y)∈E(H)(x,y) \in E(H), there exists a subgraph embedding φ\varphi of HH in GG such that φ(x)=u\varphi(x)=u and φ(y)=v\varphi(y)=v;

  • WAU (Weakly Arc Universal) if for any H\mathcal{H}-smooth graph G=(V,E)G=(V,E), any arc (u,v)∈E(u,v) \in E contained in a copy of HH in GG, and any arc (x,y)∈E(H)(x,y) \in E(H), there exists a subgraph embedding φ\varphi of HH in GG such that φ(x)=u\varphi(x)=u and φ(y)=v\varphi(y)=v;

  • AS (Arc Separating) if for any H\mathcal{H}-smooth graph G=(V,E)G=(V,E) and any arc e=(x,y)∈Ee=(x,y) \in E such that ee is contained in a copy of HH in $G there exists a copy of HH that contains xx and does not contain yy.

For a VU graph H\mathcal{H}, each vertex vv in an H\mathcal{H}-smooth graph GG is contained in a copy of H\mathcal{H} such that vv corresponds to a vertex of the maximal degree in HH. So, the following corollary is immediate.

Corollary 2.3. Let H=(H,s,t)\mathcal{H}=(H,s,t) be VU and let GG be H\mathcal{H}-smooth. Then Δ(H)≤δ(G)\Delta(H) \le\delta(G).

In general, the relations between pairs of concepts among (W)VU, (W)AU, and AS are open except for the trivial implications: VU implies WVU, AU implies WAU, AU implies VU, and WAU implies WVU.

Lemma 2.4. For a two-rooted graph H=(H,s,t)\mathcal{H}=(H,s,t) with δ(H)=1\delta(H)=1, WVU implies VU.

Proof. Let V0V_0 be the union of vertex sets of all copies of HH in an H\mathcal{H}-smooth graph G=(V,E)G=(V,E). Then, V0≠∅V_0 \ne\varnothing. Let xy∈Exy \in E be an edge such that x∈V0x \in V_0. Since H\mathcal{H} is WVU, there exists a subgraph embedding φ:V(H)→V(G)\varphi: V(H) \to V(G) such that φ−1(x)\varphi^{-1}(x) is a neighbor of a pendant vertex hh in HH. If yy is contained in φ(V(H))\varphi(V(H)), then y∈V0y \in V_0. Otherwise, substituting φ(h)\varphi(h) by yy we get another copy of HH in GG and this copy contains yy. Therefore y∈V0y \in V_0. So, y∈V0y \in V_0 in any case. Thus, V0=VV_0=V since GG is connected. This implies that H\mathcal{H} is VU. □

In the inherence proofs below we need AS and we derive it from WAU. But we are not aware of a general implication ‘WAU implies AS’, even for PE-inherent two-rooted trees. Nonetheless, the following partial result will be helpful. For the statement we need one more definition.

Definition 2.5. A two-rooted graph H=(H,s,t)\mathcal{H}=(H,s,t) is EM (Extension Movable) if the extension graph of H\mathcal{H} contains more than one copy of HH.

It is clear from the definition that every PE-inherent two-rooted tree is EM (otherwise it would be confined by its extension graph).

Lemma 2.6. If a connected two-rooted graph H=(H,s,t)\mathcal{H}=(H,s,t) is EM and WAU, then H\mathcal{H} is AS.

Proof. Let G=(V,E)G=(V,E) be a H\mathcal{H}-smooth graph and let e=(x,y)e=(x,y) be an arc of GG that is contained in a copy of HH in GG. Since H\mathcal{H} is EM, in the extension graph TT of H\mathcal{H} we can choose a copy H′H' of HH different from HH. Furthermore, we can choose an arc (h1,h2)(h_1,h_2) of HH such that h1∈V(H′)h_1\in V(H') and h2∉V(H′)h_2\notin V(H'). Such an arc does exist, since TT is connected, any edge in E(H′)∖E(H)E(H')\setminus E(H) is pendant, thus, any path in TT from a vertex in V(H′)∖V(H)V(H')\setminus V(H) to a vertex in V(H)∖V(H′)V(H)\setminus V(H') has an arc that (h1,h2)(h_1,h_2) of HH such that h1∈V(H′)h_1\in V(H') and h2∉V(H′)h_2\notin V(H'). Since H\mathcal{H} is WAU, there exists a copy H′\mathcal{H}' of H\mathcal{H} in GG such that h1h_1 corresponds to xx and h2h_2 corresponds to yy. Since GG is H\mathcal{H}-smooth, H′\mathcal{H}' has an extension in GG. Choose in the extension graph a copy H′′H'' of HH such that x∈V(H′′)x\in V(H'') and y∉V(H′′)y\notin V(H''). □

In verifying WAU for a two-rooted graph H=(H,s,t)\mathcal{H}=(H,s,t), it is helpful to use the following equivalence relation on the set of arcs of HH.

Definition 2.7. For graphs GG and HH, two arcs e1e_1 and e2e_2 of HH are GG-equivalent if there are two subgraph embeddings φ1,φ2\varphi_1,\varphi_2 of HH in GG such that φ1(e1)=φ2(e2)\varphi_1(e_1)=\varphi_2(e_2). We denote this relation as e1∼Ge2e_1\sim_G e_2.

For any two graphs GG and HH, the relation ∼G\sim_G is an equivalence relation on the set of arcs of HH. Indeed, it is reflexive and symmetric by definition. Furthermore, since a composition of isomorphisms is an isomorphism, this relation is transitive.6

The following lemma follows immediately from the definitions. We state it explicitly for future reference.

Lemma 2.8. A two-rooted graph H=(H,s,t)\mathcal{H}=(H,s,t) is WAU if for every H\mathcal{H}-smooth graph GG, every two arcs of HH are GG-equivalent to each other.

Now we turn to an important property sufficient for the existence of an avoidable copy. Let (⟨H⟩,⟨s⟩,⟨t⟩)(\langle H\rangle,\langle s\rangle,\langle t\rangle) be a copy of (H,s,t)(H,s,t) in a graph G=(V,E)G=(V,E) such that G−V(⟨H⟩)G-V(\langle H\rangle) is connected. Then the copy is avoidable: every extension has endpoints in V∖V(⟨H⟩)V\setminus V(\langle H\rangle) and they are connected by a path inside V∖V(⟨H⟩)V\setminus V(\langle H\rangle). Note that this property does not depend on roots.

Definition 2.9. Given two graphs G=(V,E)G=(V,E) and HH, the graph GG has the HH-Connected Complement property) (HH-CC property for short) if there exists a copy H′H' of HH in GG such that G−V(H′)G-V(H') is connected.

Definition 2.10. A two-rooted graph H=(H,s,t)\mathcal{H}=(H,s,t) is a CCS graph (Connected Complement or Simplicial) if every H\mathcal{H}-smooth graph has the HH-CC property.

It follows immediately from the definition that every CCS two-rooted graph is inherent. More concepts and notations are needed in the proofs of the CCS property.

Definition 2.11. Let HH be a graph. For a graph G=(V,E)G=(V,E), a pair (U,R)(U,R) of subsets of VV is HH-avoiding if {U,R}\{U,R\} is a partition of VV, the subgraph of GG induced by UU is connected, and the subgraph of GG induced by RR contains a copy of HH. An HH-avoiding pair (U,R)(U,R) is called inclusion-maximal if no HH-avoiding pair (U′,R′)(U',R') satisfies U⊂U′U \subset U'.

For graphs GG and HH, an HH-avoiding pair (U,R)(U,R) in GG, and x∈Rx\in R, we denote by RxR_x the graph G[R∖{x}]G[R\setminus\{x\}].7 Note that an inclusion-maximal HH-avoiding pair in a graph GG satisfies the hitting condition: if x∈NG(U)x\in N_G(U) then RxR_x contains no copies of HH. In other words, each copy of HH in G[R]G[R] contains NG(U)N_G(U). Otherwise, if r∈NG(U)r\in N_G(U) is not covered by the copy, then the set UU can be extended by a vertex rr preserving the properties of an HH-avoiding pair. Later we will need the following property, which is a simple implication of the hitting condition.

Proposition 2.12. Let H=(H,s,t)\mathcal{H}=(H,s,t) be a two-rooted tree, (U,R)(U,R) an inclusion-maximal HH-avoiding pair in a H\mathcal{H}-smooth graph G=(V,E)G=(V,E), and x∈NG(U)x\in N_G(U). Then xx has a neighbor in each component of RxR_x.

Proof. Suppose for contradiction that NG(x)∩C=∅N_G(x)\cap C=\varnothing for some component CC of RxR_x.8 Since GG is connected, C∩NG(U)≠∅C\cap N_G(U)\ne\varnothing. Let y∈C∩NG(U)y\in C\cap N_G(U). The hitting condition implies that there exists a copy ⟨H⟩\langle H\rangle of HH containing xx and yy. Let PP be a shortest path from xx to yy in ⟨H⟩\langle H\rangle. Then, all the vertices of PP except xx belong to CC, implying that NG(x)∩C≠∅N_G(x)\cap C\ne\varnothing, a contradiction.

Definition 2.13. A two-rooted graph H=(H,s,t)\mathcal{H}=(H,s,t) is HCS (H-Component is Small) if for any H\mathcal{H}-smooth graph GG and any inclusion-maximal HH-avoiding pair (U,R)(U,R) in GG, the following implication holds: if there exists a vertex x∈NG(U)x\in N_G(U) such that RxR_x is connected, then ∣R∣=∣V(H)∣|R|=|V(H)|.

The HCS property implies the HH-CC property of any H\mathcal{H}-smooth graph GG, since by definition the graph G[R]G[R] contains a copy of HH. The basic lemma for the proofs of inherence is as follows.

Lemma 2.14. If a two-rooted graph H=(H,s,t)\mathcal{H}=(H,s,t) is AS, AU, and HCS, then it is CCS.

As an immediate corollary we get that any AS, AU, and HCS graph is inherent.

Proof. Take an H\mathcal{H}-smooth graph G=(V,E)G=(V,E) and an inclusion-maximal H\mathcal{H}-avoiding pair (U,R)(U,R) in GG.

We claim that for every vertex x∈NG(U)x\in N_G(U), every connected component CC of RxR_x satisfies NG(U)∩C≠∅N_G(U)\cap C\ne\varnothing. We prove the claim by contradiction. Suppose that NG(U)∩C=∅N_G(U)\cap C=\varnothing for some component CC of RxR_x, where x∈NG(U)x\in N_G(U). Then, CC is a component in G−xG-x, since NG(U)∩C=∅N_G(U)\cap C=\varnothing. It follows from Proposition 2.12 that there exists an edge xv∈Exv\in E such that v∈Cv\in C. Since H\mathcal{H} is AU, there exists a copy of HH in GG that contains the arc (v,x)(v,x). Hence, as H\mathcal{H} is AS, there is a copy of HH that contains vv and does not contain xx. This copy should be contained in CC since NG(C)={x}N_G(C)=\{x\}. Thus (U∪{x},R∖{x})(U\cup\{x\},R\setminus\{x\}) is an H\mathcal{H}-avoiding pair, contradicting the maximality of (U,R)(U,R).

For x∈NG(U)x\in N_G(U), let Rx,1,Rx,2,…,Rx,sR_{x,1},R_{x,2},\ldots,R_{x,s} be the connected components of RxR_x ordered non-increasingly by size, and let rx,i=∣Rx,i∣r_{x,i}=|R_{x,i}| for all 1≤i≤s1\le i\le s. Then rx,1≥rx,2≥⋯≥rx,sr_{x,1}\ge r_{x,2}\ge\cdots\ge r_{x,s}. Choose x∈NG(U)x\in N_G(U) such that the vector rx=(rx,1,rx,2,…,rx,s)\mathbf{r}_x=(r_{x,1},r_{x,2},\ldots,r_{x,s}) is maximal with respect to the lexicographic order. We claim that RxR_x is connected. Since H\mathcal{H} is HCS, this implies that H\mathcal{H}-CC property of GG does hold and, consequently, that H\mathcal{H} is CCS.

Now, we prove the claim. Suppose for contradiction that s≥2s\ge2. By Proposition 2.12, xx has a neighbor ww in Rx,2R_{x,2}. Then, Rx,2∩NG(U)=∅R_{x,2}\cap N_G(U)=\varnothing due to the maximality in the lexicographic order, since if v∈Rx,2∩NG(U)v\in R_{x,2}\cap N_G(U), then the vector rv\mathbf{r}_v is lexicographically larger than rx\mathbf{r}_x (the component Rx,1R_{x,1} is enlarged by at least xx by Proposition 2.12). As we have seen before, this is impossible. Hence, we come to a contradiction. □

Figure 1 summarizes the implications between various properties of two-rooted graphs studied in this paper. For convenience of the reader, we collect in Appendix § 9 abbreviations of various properties used in this paper.

Inherent paths

Here we extend Theorem 1.3 to the NNI setting and prove the following variant of Theorem 1.4, thus completely characterizing inherent two-rooted paths.

Theorem 3.1. For every two-rooted path H\mathcal{H}, the following properties are equivalent.

(a) H\mathcal{H} is inherent.

(b) H\mathcal{H} satisfies the NCI property.

(c) H\mathcal{H} is T1(l,0,l′)T_1(l,0,l') for some l≥1l\ge1 and l′≥0l'\ge0.

(d) H\mathcal{H} is CCS.

Remark 3.2. Recall that the concepts of inherence differ in the induced [11] and NNI settings. In particular, it was proved in [11] that T1(2,0,2)T_1(2,0,2) is confined by the Petersen graph in the induced setting.

The implication (a)⇒(b)(a) \Rightarrow(b) holds for general connected two-rooted graphs (cf. Observation 1.2), while the implications and (d)⇒(a)(d) \Rightarrow(a) and (b)⇒(c)(b) \Rightarrow(c) are immediate consequences of the definitions. Hence, it remains to show that every two-rooted graph of the form T1(l,0,l′)T_1(l,0,l'), with l≥1l \ge1 and l′≥0l' \ge0, is CCS. In subsequent analysis we denote the number of vertices by n=l+l′n = l + l'. In the case n=1n = 1 the implication follows from a well-known fact that in every connected graph with at least two vertices there exists a vertex such whose removal results in a connected graph. So, from now on we assume that n≥2n \ge2. We prove the implication by showing that T1(l,0,l′)T_1(l,0,l') is AS and AU, as well as HCS, in the course of Lemmas 3.3 and 3.4, and then applying Lemma 2.14.

Lemma 3.3. T1(l,0,l′)T_1(l,0,l') is AS and AU.

Proof. The extension graph of T1(l,0,l′)T_1(l,0,l') contains a path Pn+1P_{n+1}. Thus it contains at least two paths PnP_n. So, T1(l,0,l′)T_1(l,0,l') is EM.

Next, we prove that T1(l,0,l′)T_1(l,0,l') is WAU. For this purpose we fix a T1(l,0,l′)T_1(l,0,l')-smooth graph GG and use the GG-equivalence relation on arcs of T1(l,0,l′)T_1(l,0,l'). Let a1,…,ana_1,\ldots,a_n be the vertices of T1(l,0,l′)T_1(l,0,l') and ei={ai,ai+1}e_i = \{a_i,a_{i+1}\}, 1≤i≤n−11 \le i \le n-1 be its edges. Arcs of T1(l,0,l′)T_1(l,0,l') are ei+=(ai,ai+1)e_i^+ = (a_i,a_{i+1}) and ei−=(ai+1,ai)e_i^- = (a_{i+1},a_i), 1≤i≤n−11 \le i \le n-1.

Let P=(x1,…,xn)P = (x_1,\ldots,x_n) be a copy of PnP_n in a T1(l,0,l′)T_1(l,0,l')-smooth graph G=(V,E)G = (V,E). Note that P′=(xn,…,x1)P' = (x_n,\ldots,x_1) is also a copy of T1(l,0,l′)T_1(l,0,l') in GG. Since GG is T1(l,0,l′)T_1(l,0,l')-smooth, both endpoints x1x_1, xnx_n are roots of non-simplicial copies of T1(l,0,l′)T_1(l,0,l'), both of them have neighbors in V∖V(P)V \setminus V(P), say x0x1∈Ex_0x_1 \in E, xn+1xn∈Ex_{n+1}x_n \in E such that x0≠xix_0 \ne x_i, xn+1≠xix_{n+1} \ne x_i for 1≤i≤n1 \le i \le n (it is possible that x0=xn+1x_0 = x_{n+1} if l′≠0l' \ne0).

Looking at the path (x0,…,xn−1)(x_0,\ldots,x_{n-1}) we see ei+∼Gei+1+e_i^+ \sim_G e_{i+1}^+ and ei−∼Gei+1−e_i^- \sim_G e_{i+1}^- for 1≤i<n−11 \le i < n-1. So all ei+e_i^+ are GG-equivalent as well as all ei−e_i^-. Now look at the copy P′=(xn,…,x1)P' = (x_n,\ldots,x_1) of T1(l,0,l′)T_1(l,0,l') in GG. Comparing PP and P′P' shows that e1+∼Gen−1−e_1^+ \sim_G e_{n-1}^- and e1−∼Gen−1+e_1^- \sim_G e_{n-1}^+. Thus every two arcs of T1(l,0,l′)T_1(l,0,l') are GG-equivalent to each other and, due to Lemma 2.8, T1(l,0,l′)T_1(l,0,l') is WAU and thus also WVU. Lemma 2.6 implies that T1(l,0,l′)T_1(l,0,l') is also AS.

To conclude the proof we now show that T1(l,0,l′)T_1(l,0,l') is AU. Since n≥2n \ge2, by Lemma 2.4, T1(l,0,l′)T_1(l,0,l') is VU. Let G=(V,E)G=(V,E) be an T1(l,0,l′)T_1(l,0,l')-smooth graph, (x,y)∈E(x,y) \in E be an arc. By VU, there exists a copy (x1,…,xn)(x_1,\ldots,x_n) of T1(l,0,l′)T_1(l,0,l') such that x1=xx_1=x. We distinguish the following cases:

  • If y=x2y=x_2, we are done.

  • If y=xiy=x_i for some i>2i>2, the copy (xi−1,xi−2,…,x1,xi,xi+1,…,xn−1,xn)(x_{i-1},x_{i-2},\ldots,x_1,x_i,x_{i+1},\ldots,x_{n-1},x_n) contains the arc (x,y)(x,y).

  • Otherwise, the copy (xn−1,…,x1,y)(x_{n-1},\ldots,x_1,y) contains the arc (x,y)(x,y).

So, in all cases the arc (x,y)(x,y) is in a copy of T1(l,0,l′)T_1(l,0,l'). Now AU follows from the fact that T1(l,0,l′)T_1(l,0,l') is WAU.

Lemma 3.4. T1(l,0,l′)T_1(l,0,l') is HCS.

Proof. Let G=(V,E)G=(V,E) be an T1(l,0,l′)T_1(l,0,l')-smooth graph, (U,R)(U,R) be an inclusion-maximal PnP_n-avoiding pair in GG, and P=(a1,…,an)P=(a_1,\ldots,a_n) be a copy of PnP_n in G[R]G[R]. Since GG is T1(l,0,l′)T_1(l,0,l')-smooth, both endpoints a1a_1, ana_n of PP are roots of non-simplicial copies of T1(l,0,l′)T_1(l,0,l'), hence, both of them have neighbors outside of V(P)V(P). We now show that either NG({a1,an})∖V(P)⊆UN_G(\{a_1,a_n\}) \setminus V(P) \subseteq U (in which case PP is an outer path) or {a1,an}∩NG(U)=∅\{a_1,a_n\} \cap N_G(U)=\emptyset (in which case PP is an inner path).

Suppose that a1∉NG(U)a_1 \notin N_G(U) and an∈NG(U)a_n \in N_G(U). An extension of a copy of T1(l,0,l′)T_1(l,0,l') gives an edge a0a1∈Ea_0a_1 \in E such that a0∈R∖V(P)a_0 \in R \setminus V(P). We get a copy (a0,a1,…,an−1)(a_0,a_1,\ldots,a_{n-1}) of T1(l,0,l′)T_1(l,0,l') in RanR_{a_n}, a contradiction with the hitting condition. Similarly, we obtain a contradiction if an∉NG(U)a_n \notin N_G(U) and a1∈NG(U)a_1 \in N_G(U). Hence, either none of a1,ana_1,a_n has a neighbor in UU or both of them have neighbors in UU. In the second case neither of a1,ana_1,a_n has a neighbor in R∖V(P)R \setminus V(P) due to the same argument. Consequently, PP is an inner path in the former case and an outer path in the latter case. Note that we have proved that if one of the endpoints of PP has a neighbor in UU, then PP is outer, and if not, it is an inner path.

Assume that PP is an outer path, a1,an∈NG(U)a_1,a_n \in N_G(U). To complete this case, let us prove by contradiction that R∖V(P)=∅R \setminus V(P)=\emptyset (which is equivalent to ∣R∣=n|R|=n). Suppose that R∖V(P)≠∅R \setminus V(P)\ne\emptyset. Due to the hitting condition, there is no edge in GG connecting a vertex in UU with a vertex in R∖V(P)R \setminus V(P). This implies that V(P)V(P) is a cut set in GG. Hence, there exists an edge akra_kr such that r∈R∖V(P)r \in R \setminus V(P) and k∈[n]k \in[n]. Let kk be the smallest number satisfying this condition. Since PP is an outer path, 1<k<n1<k<n. Choose (v1,v2,…,vq)(v_1,v_2,\ldots,v_q) as a longest path in G[(R∖V(P))∪{ak}]G[(R \setminus V(P)) \cup\{a_k\}] starting at ak=v1a_k=v_1. Due to maximality of UU, q<kq<k: otherwise, the path (vq,vq−1,…,v1,ak+1,…,an)(v_q,v_{q-1},\ldots,v_1,a_{k+1},\ldots,a_n) contains a subpath with nn vertices that does not contain a1∈NG(U)a_1 \in N_G(U), which is impossible due to the hitting condition. Since a1a_1, ana_n have neighbors u′,u′′u',u'' in UU and G[U]G[U] is connected, there exists a cycle (a1,…,an,an+1,…,an+j,a1)(a_1,\ldots,a_n,a_{n+1},\ldots,a_{n+j},a_1), where ai∈Ua_i \in U for all n<i≤n+jn<i\le n+j and u′=an+ju'=a_{n+j}, u′′=an+1u''=a_{n+1}.

Take a copy F=(vq,vq−1,…,ak,ak+1,…,ak+n−q)F=(v_q,v_{q-1},\ldots,a_k,a_{k+1},\ldots,a_{k+n-q}) of PnP_n (indices in aia_i are taken modulo n+jn+j). Furthermore, this copy is simplicial in GG: there are no edges from vqv_q to UU due to the hitting condition, there are no edges from vqv_q to aia_i, i<ki<k, by the choice of kk, for all k≤i≤nk\le i\le n the vertex aia_i belongs to FF since q<kq<k, and, finally, there are no edges from vqv_q to R∖V(P)R\setminus V(P) since the path v1,v2,…,vqv_1,v_2,\ldots,v_q is a longest one. We get a contradiction, since GG has no simplicial copies of T1(l,0,l′)T_1(l,0,l').

By the previous arguments, we may assume that all the copies of PnP_n in G[R]G[R] are inner paths. To complete the proof, we verify that if there exists a vertex x∈NG(U)x\in N_G(U) such that RxR_x is connected, then ∣R∣=∣V(H)∣|R|=|V(H)|. Fix x∈NG(U)x\in N_G(U) such that RxR_x is connected. Due to the hitting condition, xx is contained in every copy of PnP_n in G[R]G[R]. Choose the minimal qq such that x=xqx=x_q in a copy (x1,…,xn)(x_1,\ldots,x_n) of PnP_n in G[R]G[R]. Suppose that q>1q>1. Take an extension (xn+1,xn,…,x1;z)(x_{n+1},x_n,\ldots,x_1;z) of a copy (xn,…,x1)(x_n,\ldots,x_1), where xnxn+1x_nx_{n+1} and xn−l+1zx_{n-l+1}z are extension edges. If xn+1∈Ux_{n+1}\in U, then the path (xn,…,x1)(x_n,\ldots,x_1) is outer, a contradiction. Otherwise, since q≥2q\ge2, the copy (x2,…,xn+1)(x_2,\ldots,x_{n+1}) of PnP_n contains the vertex x=xqx=x_q, moreover, this vertex corresponds to the (q−1)(q-1)-the vertex of the path, a contradiction with the definition of qq. Thus q=1q=1 and x=x1x=x_1. Similar arguments show that, since (x1,x2,…,xn)(x_1,x_2,\ldots,x_n) is an inner path, we come to a contradiction with the hitting condition.

Theorem 1.4 follows from Lemmas 3.3 and 3.4 applied to Lemma 2.14.

Inherent forks

Recall that the fork F(1,1,2)F(1,1,2) (or, equivalently, F(2,1,1)F(2,1,1)) is the unique 5-vertex tree with maximum degree 3. We denote a fork with vertex set {v1,…,v5}\{v_1,\ldots,v_5\} and edge set {v1v2,v2v3,v3v4,v3v5}\{v_1v_2,v_2v_3,v_3v_4,v_3v_5\} by v1v2v3v4v5v_1v_2v_3v_4v_5. We prove in Section B.2 that there are exactly three two-rooted fork graphs that are PE-inherent. They are shown in Figure 2 to Figure 4. For later use, we identify the vertices of the graphs as shown in this figure and denote a copy of the corresponding graph by the sequence shown in the figure. Below we refer to these two-rooted graphs as PE-forks.

Theorem 4.1. PE-forks are CCS graphs. Hence, they are inherent.

Due to Lemma 2.14, to prove Theorem 4.1 it is enough to prove that a PE-fork is AS, AU, and HCS.

Lemma 4.2. A PEPE-fork FF is ASAS and AUAU.

Proof. In Figure 5(b-Figure 5d) the extension graphs for PEPE-forks are shown, together with the labels of vertices that we use in this proof.

It is easy to verify that PEPE-forks are EMEM: for T1(2,1,1)T_1(2,1,1) an additional copy is, e.g., (b,a,t,s,v2)(b,a,t,s,v_2); for T3(1,1)T_3(1,1) an additional copy is, e.g., (s,a,t,c,v2)(s,a,t,c,v_2); for T1(1,1,2)T_1(1,1,2) an additional copy is, e.g., (v2,s,a,b,c)(v_2,s,a,b,c).

Naming arcs of the fork and extension graphs of PE-forks

Figure 5. Naming arcs of the fork; and the extension graphs of PE-forks.

Next, we prove that FF is WAUWAU. For this purpose we use Lemma 2.8. So, we are going to prove that for every FF-smooth graph GG, all arcs of FF are GG-equivalent. Name (some of the) arcs of the fork as shown in Figure 5(a). Note that it is enough to consider only three pairs of arcs due to automorphisms of the fork, since arcs in the same orbit of the automorphism group are obviously equivalent.

Now we compare arcs in the original copy and additional copies in its extensions in GG. Let F=T1(2,1,1)F=T_1(2,1,1) and GG be a T1(2,1,1)T_1(2,1,1)-smooth graph. The copy (b,a,t,s,v2)(b,a,t,s,v_2) of T1(2,1,1)T_1(2,1,1) shows that 1∼G3′1\sim_G3', 1′∼G31'\sim_G3, 2∼G2′2\sim_G2'. Furthermore, the copy (v1,s,t,a,v2)(v_1,s,t,a,v_2) gives equivalences 1∼G21\sim_G2, 1′∼G2′1'\sim_G2', 2∼G32\sim_G3, 2′∼G3′2'\sim_G3'. Hence, all arcs of FF are GG-equivalent:

3∼G1′∼G2′∼G2∼G1∼G3′3\sim_G1'\sim_G2'\sim_G2\sim_G1\sim_G3'

We conclude from Lemma 2.8 that T1(2,1,1)T_1(2,1,1) is WAUWAU.

Let F=T3(1,1)F=T_3(1,1) and GG be a T3(1,1)T_3(1,1)-smooth graph. The copy (b,a,t,c,v2)(b,a,t,c,v_2) of T3(1,1)T_3(1,1) shows that 1∼G3′1\sim_G3', 1′∼G31'\sim_G3, 2∼G2′2\sim_G2', see Figure 5(c). The copy (v1,s,a,t,b)(v_1,s,a,t,b) shows that 3∼G2′3\sim_G2', 3′∼G23'\sim_G2. So, all arcs of T3(1,1)T_3(1,1) are GG-equivalent:

1′∼G3∼G2′∼G2∼G3′∼G1.1'\sim_G3\sim_G2'\sim_G2\sim_G3'\sim_G1.

From Lemma 2.8 we conclude that T3(1,1)T_3(1,1) is WAUWAU.

Finally, we consider the case F=T1(1,1,2)F=T_1(1,1,2). This case is more complicated. Let GG be a T1(1,1,2)T_1(1,1,2)-smooth graph. The copy (v2,s,a,b,c)(v_2,s,a,b,c) from the extension graph in Figure 5(d) gives equivalences 3∼G2′3\sim_G2', 3′∼G23'\sim_G2. One more copy of T1(1,1,2)T_1(1,1,2) in the extension graph gives the same equivalences. So, we take an extension of (v2,s,a,b,c)(v_2,s,a,b,c), which gives an edge cv3cv_3, v3≠ev_3\ne e and a new copy (s,a,c,e,v3)(s,a,c,e,v_3). The copy gives equivalences 3∼G1′3\sim_G1', 3′∼G13'\sim_G1, 2∼G2′2\sim_G2'. So, all arcs of T1(1,1,2)T_1(1,1,2) are GG-equivalent:

1′∼G3∼G2′∼G2∼G3′∼G1,1'\sim_G3\sim_G2'\sim_G2\sim_G3'\sim_G1,

and an application of Lemma 2.8 shows that T1(1,1,2)T_1(1,1,2) is WAU.

Since PE-forks are EM and WAU, they are AS due to Lemma 2.6.

It remains to prove that PE-forks are AU. Let F\mathcal{F} be a PE-fork and G=(V,E)G=(V,E) be an F\mathcal{F}-smooth graph. Take an arc (x,y)(x,y) in GG. Since F\mathcal{F} is WAU, it is WVU by a direct implication and VU by Lemma 2.4. Take a copy of F\mathcal{F} containing xx. If the copy contains also xyxy, we are done, since F\mathcal{F} is WAU. If not, there should be an edge xzxz in the copy. Since F\mathcal{F} is WAU, this implies that there exists a copy of F\mathcal{F} such that the arc (x,z)(x,z) corresponds to the arc from the vertex of degree 2 to the vertex of degree 3 in the fork. If this copy contains the edge xyxy, we are done. If the copy does not contain yy, then substitute a pendant vertex adjacent to xx by yy, and we are also done. The remaining case is unique up to isomorphism, it is shown in Figure 6. In this case xyxy is an edge of the copy (v2,z,x,y,v1)(v_2,z,x,y,v_1). Since F\mathcal{F} is WAU, this completes

Figure 6. The special case in the proof of AU for a PE-fork.

the proof that F\mathcal{F} is AU.

To prove that PE-forks are HCS, we will need the following claim about fork-free graphs, that is, graphs containing no copies of the fork.

Lemma 4.3. Any connected fork-free graph on at least 5 vertices is either a star K1,nK_{1,n}, a path PnP_n, or a cycle CnC_n for some nn.

Proof. Let G=(V,E)G=(V,E) be a connected fork-free graph with ∣V∣≥5|V| \ge5. If all vertices in GG have degree at most 2 then GG is path or a cycle, since GG is connected. From now on assume that there exists v∈Vv \in V such that dG(v)≥3d_G(v) \ge3. We need to prove that G≅K1,nG \cong K_{1,n} (for n=∣V∣−1n=|V|-1).

Suppose the contrary. Since GG is connected, there exists an edge xy∈Exy \in E, x∈N(v)x \in N(v), y≠vy \ne v. If dG(v)=3d_G(v)=3, then, since GG has at least 5 vertices, we may assume that yy is chosen outside N(v)N(v), and we obtain a copy yxvv1v2yxvv_1v_2 of the fork, where v1,v2∈N(v)v_1,v_2 \in N(v) with v1≠v2v_1 \ne v_2. If dG(v)≥4d_G(v) \ge4, then choose v1,v2∈N(v)∖{x,y}v_1,v_2 \in N(v) \setminus\{x,y\} and get a copy yxvv1v2yxvv_1v_2 of the fork. Thus, GG is not fork-free, a contradiction.

Lemma 4.4. A PE-fork F\mathcal{F} is HCS.

Proof. Let G=(V,E)G=(V,E) be an F\mathcal{F}-smooth graph, and (U,R)(U,R) be an inclusion-maximal F\mathcal{F}-avoiding pair (U,R)(U,R) in GG, and x∈NG(U)x \in N_G(U) such that RxR_x is connected. Since F\mathcal{F} is AU by Lemma 4.2, F\mathcal{F} is also VU. Hence, by Corollary 2.3, we have δ(G)≥3\delta(G) \ge3.

We are going to prove that ∣R∣=∣V(F)∣=5|R|=|V(\mathcal{F})|=5. So we need to exclude the case when ∣R∣>5|R|>5. Note that in this case ∣V(Rx)∣≥5|V(R_x)| \ge5 and RxR_x is fork-free due to the hitting condition. From Lemma 4.3 we conclude that there are exactly three possible cases for RxR_x.

Case Rx=K1,nR_x=K_{1,n}, n≥4n \ge4. Let viv_i be pendant vertices of the star RxR_x. Then dG(vi)≥δ(G)≥3d_G(v_i) \ge\delta(G) \ge3. This implies that vi∈NG(U)v_i \in N_G(U) for all ii, since there are only two possible edges in G[R]G[R] incident to viv_i: the edge vizv_i z, where zz is the center of the star and (possibly) the edge vixv_i x. Therefore {x,v1,v2,v3,v4}⊆NG(U)\{x,v_1,v_2,v_3,v_4\} \subseteq N_G(U). By the hitting condition, each copy of the fork in G[R]G[R] contains NG(U)N_G(U), and therefore G[{x,v1,v2,v3,v4}]G[\{x,v_1,v_2,v_3,v_4\}] is a fork. We come to a contradiction, since G[{x,v1,v2,v3,v4}]G[\{x,v_1,v_2,v_3,v_4\}] has an independent set of size 4 and the fork does not.

Case Rx=PnR_x=P_n, n≥5n\geq5. Enumerate vertices along the path: v1,v2,…,vnv_1,v_2,\ldots,v_n, where n≥5n\geq5. Since dG(vi)≥δ(G)≥3d_G(v_i)\geq\delta(G)\geq3, {v1,vn}∈NG(U)\{v_1,v_n\}\in N_G(U). Furthermore, since any copy of the fork should contain the set NG(U)N_G(U), the graph Rv1R_{v_1} is fork-free and, since the fork has only 5 vertices, there exists a vertex viv_i in the path such that vi∉NG(U)v_i\notin N_G(U) and therefore xvi∈Exv_i\in E. Since n≥5n\geq5 and the path is induced, viv_i is not adjacent to at least one endpoint of the path. By symmetry, we may assume that i>2i>2. Notice that the connected component R′R' of the graph Rv1R_{v_1} that contains the vertex viv_i satisfies ∣V(R′)∣≥5|V(R')|\geq5, since R′R' contains all the vertices vjv_j for j>1j>1, as well as vertex xx. Since viv_i has degree 3 in R′R', we conclude that R′R' is neither a star, nor a path, nor a cycle. Since R′R' is fork-free, this contradicts Lemma 4.3.

Case Rx=CnR_x=C_n, n≥5n\geq5. Again, there exists a vertex vv in the cycle such that v∉NG(U)v\notin N_G(U). Since dG(v)≥δ(G)≥3d_G(v)\geq\delta(G)\geq3, we conclude that vx∈Evx\in E. Enumerate vertices along the cycle starting from vv: v1,v2,…,vnv_1,v_2,\ldots,v_n, v1=vv_1=v, where n≥5n\geq5. For 3≤i≤n−13\leq i\leq n-1, in the connected component R′R' of the graph RviR_{v_i} that contains the vertex v1v_1, the vertex v1v_1 has degree at least 3 (due to the edges v1xv_1x, v1v2v_1v_2, and v1vnv_1v_n) and, moreover, ∣V(R′)∣≥5|V(R')|\geq5, since R′R' contains at least four vertices of the cycle, as well as vertex xx. Since v1v_1 has degree at least 3 in R′R', we conclude that R′R' is neither a star, nor a path, nor a cycle. By Lemma 4.3, R′R' contains a copy of the fork and, hence, so does RviR_{v_i}. By the hitting condition, this implies that vi∉NG(U)v_i\notin N_G(U), hence, the only possible neighbors of viv_i in GG are xx, vi−1v_{i-1}, and vi+1v_{i+1}. Since also dG(vi)≥δ(G)≥3d_G(v_i)\geq\delta(G)\geq3, we conclude that dG(vi)=3d_G(v_i)=3 and, moreover, xvi∈Exv_i\in E for 3≤i≤n−13\leq i\leq n-1. This leads to a contradiction with the fact that GG is F\mathcal{F}-smooth, since a simplicial copy of F\mathcal{F} does exist under these conditions, see Figure 7, where simplicial copies are shadowed.

Figure 7. Simplicial copies: (v5,v4,v3,v2,x)(v_5,v_4,v_3,v_2,x) for T1(2,1,1)T_1(2,1,1) and for T3(1,1)T_3(1,1) (on the left); (v1,x,v3,v2,v4)(v_1,x,v_3,v_2,v_4) for T1(1,1,2)T_1(1,1,2) (on the right).

Theorem 4.1 follows from Lemmas 4.2 and 4.4 applied to Lemma 2.14.

Proof of Theorem 1.5

Let recall the statement of the theorem.

Theorem 1.5. T1(2,1,2)T_1(2,1,2) is inherent.

The proof of Theorem 1.5 is similar to the proofs for PE-forks. In fact, we conjecture that T1(2,1,2)T_1(2,1,2) is CCS; however, the analysis is much more involved. Inherence is easier to prove than CCS, since we can stop our analysis whenever an avoidable copy is detected.

We will indicate a copy of T1(2,1,2)T_1(2,1,2) by a sequence of vertices in the order shown in Figure 8(a). For the purpose of analyzing GG-equivalence with respect to some T1(2,1,2)T_1(2,1,2)-smooth graph GG, we name arcs of T1(2,1,2)T_1(2,1,2) as shown in Figure 8(b). Due to automorphisms of T1(2,1,2)T_1(2,1,2), it is enough to consider only three pairs of arcs.

Lemma 5.1. T1(2,1,2)T_1(2,1,2) is WAU.

Proof. Let GG be a T1(2,1,2)T_1(2,1,2)-smooth graph. We fix a copy (s,t,a,b,c,d)(s,t,a,b,c,d) of T1(2,1,2)T_1(2,1,2) in GG and an extension of it using edges sv1sv_1 and tv2tv_2, as shown in Figure 9.

Figure 9. An extension of T1(2,1,2)T_1(2,1,2).

Let us compare the initial copy of T1(2,1,2)T_1(2,1,2) and the copy (v1,s,t,a,d,v2)(v_1,s,t,a,d,v_2) in the extension graph. This gives equivalences 1∼G21 \sim_G 2, 1′∼G2′1' \sim_G 2', 2∼G2′2 \sim_G 2', 3∼G1′3 \sim_G 1', 3′∼G13' \sim_G 1. Thus, all arcs of T1(2,1,2)T_1(2,1,2) are GG-equivalent:

3∼G1′∼G2′∼G2∼G1∼G3′,3 \sim_G 1' \sim_G 2' \sim_G 2 \sim_G 1 \sim_G 3',

and an application of Lemma 2.8 shows that T1(2,1,2)T_1(2,1,2) is WAU.

Corollary 5.2. Let GG be a T1(2,1,2)T_1(2,1,2)-smooth graph. Then δ(G)≥3\delta(G) \ge3.

Proof. Recall that WAU implies WVU. The corollary follows from Lemmas 2.4 and 5.1 and Corollary 2.3.

Lemma 5.3. Let GG be a T1(2,1,2)T_1(2,1,2)-smooth graph. Then there exists an inclusion-maximal avoiding pair (U,R)(U,R) for T1(2,1,2)T_1(2,1,2) in GG such that ∣U∣≥2|U| \ge2.

Proof. Take a copy of T1(2,1,2)T_1(2,1,2) and its extension graph shown in Figure 9. The copy (v2,t,a,b,c,d)(v_2,t,a,b,c,d) certifies that ({v1,s},V(G)∖{v1,s})\left(\{v_1,s\}, V(G) \setminus\{v_1,s\}\right) is an avoiding pair for T1(2,1,2)T_1(2,1,2) in GG. It can be extended to an inclusion-maximal avoiding pair (U,R)(U,R) and the size of UU is at least 2 in that pair.

Proof of Theorem 1.5. Suppose for a contradiction that T1(2,1,2)T_1(2,1,2) is not inherent. Then, there exists a connected confining graph GG for T1(2,1,2)T_1(2,1,2). In particular, the graph GG is T1(2,1,2)T_1(2,1,2)-smooth. By Lemma 5.3, there exists an inclusion-maximal avoiding pair (U,R)(U,R) for T1(2,1,2)T_1(2,1,2) in GG such that ∣U∣≥2|U| \ge2. Due to maximality of UU, the hitting condition holds: for each x∈R∩NG(U)x \in R \cap N_G(U), the graph Rx=G[R∖{x}]R_x = G[R \setminus\{x\}] is T1(2,1,2)T_1(2,1,2)-free.

Let A=(x1,y1,z1,y2,x2,z2)A=(x_1,y_1,z_1,y_2,x_2,z_2) (see Figure 8(a) for naming convention) be a copy of T1(2,1,2)T_1(2,1,2) contained in G[R]G[R]. Since GG is a confining graph for T1(2,1,2)T_1(2,1,2), this copy of T1(2,1,2)T_1(2,1,2) is not avoidable in GG; hence, there exists a non-closable extension by edges x1w1,y1w2x_1w_1,y_1w_2. Let R′=R∖V(A)R' = R \setminus V(A). Recall that G[U]G[U] is connected. So, if w1,w2∈Uw_1,w_2 \in U, then the extension is closable. Note that the case w1∈Uw_1 \in U, w2∈R′w_2 \in R' is impossible because in this case Rx1R_{x_1} does contain a copy (w2,y1,z1,y2,x2,z2)(w_2,y_1,z_1,y_2,x_2,z_2) of T1(2,1,2)T_1(2,1,2), in contradiction with the hitting condition. To complete the proof, we need to consider two remaining cases.

Case w1∈R′w_1 \in R', w2∈R′w_2 \in R'. First, we note that x1∉NG(U)x_1 \notin N_G(U), since otherwise we come to a contradiction with the hitting condition as explained above. From the hitting condition we also conclude that x2,y2∉NG(U)x_2,y_2 \notin N_G(U) since the graphs Rx2R_{x_2} and Ry2R_{y_2} contain the copy (w1,x1,y1,z1,z2,w2)(w_1,x_1,y_1,z_1,z_2,w_2) of T1(2,1,2)T_1(2,1,2). Let w1v1,x1v2w_1v_1,x_1v_2 be the edges of an extension of this copy. Note that it is possible that {v1,v2}∩{x2,y2}≠∅\{v_1,v_2\} \cap\{x_2,y_2\} \ne\varnothing, and v1,v2∉Uv_1,v_2 \notin U since (R′∪{x1})∩NG(U)=∅(R' \cup\{x_1\}) \cap N_G(U)=\varnothing. The copy (v1,w1,x1,y1,w2,v2)(v_1,w_1,x_1,y_1,w_2,v_2) of T1(2,1,2)T_1(2,1,2) is contained in the graphs Rz1R_{z_1} and Rz2R_{z_2}, see Figure 10 (dashed circles in the figure indicate vertices that are in R∖NG(U)R \setminus N_G(U)). This implies that z1,z2∉NG(U)z_1,z_2 \notin N_G(U). Thus NG(U)={y1}N_G(U)=\{y_1\} since this set is not empty (as GG is connected).

Figure 10. To the proof that NG(U)={y1}N_G(U)=\{y_1\}.

The copy (x2,y2,z1,y1,x1,z2)(x_2,y_2,z_1,y_1,x_1,z_2) of T1(2,1,2)T_1(2,1,2) is not avoidable. Due to the previous analysis and the fact that y2∉NG(U)y_2 \notin N_G(U), there exists an extension of the copy by edges x2v3,y2v4x_2v_3,y_2v_4, where v3,v4∈R′v_3,v_4 \in R' (see Figure 11). The copy (z2,z1,y2,x2,v3,v4)(z_2,z_1,y_2,x_2,v_3,v_4) is contained in Ry1R_{y_1} and we come to a contradiction with the hitting condition.

Figure 11. A contradiction with the hitting condition.

Case w1∈R′w_1 \in R', w2∈Uw_2 \in U. The previous case shows that w1∈R′w_1 \in R', w2∈Uw_2 \in U holds for every copy of T1(2,1,2)T_1(2,1,2) in G[R]G[R]. Take a copy A=(x1,y1,z1,y2,x2,z2)A=(x_1,y_1,z_1,y_2,x_2,z_2) and the ‘reflected’ copy A′=(x2,y2,z1,y1,x1,z2)A'=(x_2,y_2,z_1,y_1,x_1,z_2). From extensions of these copies we conclude that y1,y2∈NG(U)y_1,y_2 \in N_G(U).

Next step is to prove that x1∈NG(U)x_1 \in N_G(U). Suppose for contradiction that x1∉NG(U)x_1 \notin N_G(U). Then an extension of the copy (w1,x1,y1,z1,z2,w2)(w_1,x_1,y_1,z_1,z_2,w_2) uses edges w1v1w_1v_1, x1v2x_1v_2 such that v1,v2∉Uv_1,v_2 \notin U (see Figure 12(a)). Thus the copy (v1,w1,x1,y1,z1,v2)(v_1,w_1,x_1,y_1,z_1,v_2) should not be contained in Ry2R_{y_2}, implying that y2∈{v1,v2}y_2 \in\{v_1,v_2\}. If y2=v1y_2=v_1, then the copy (z2,z1,y2,w1,x1,x2)(z_2,z_1,y_2,w_1,x_1,x_2) is contained in Ry1R_{y_1}, in contradiction with the hitting condition (see Figure 12(b)).

Figure 12. To the proof that x1∈NG(U)x_1 \in N_G(U).

If y2=v2y_2=v_2, then the copy (z2,z1,y2,x1,w1,x2)(z_2,z_1,y_2,x_1,w_1,x_2) is contained in Ry1R_{y_1} (see Figure 12(c)). Again, we come to a contradiction. This shows that x1∈NG(U)x_1 \in N_G(U), as claimed.

Substituting AA by A′A' in the previous argument shows that x2∈NG(U)x_2 \in N_G(U) as well.

Neighbors of x1,x2,y1,y2x_1,x_2,y_1,y_2 in UU can coincide. In any case, since G[U]G[U] is connected and ∣U∣≥2|U| \ge2, there exists a path x1uu′x_1uu', where u,u′∈Uu,u' \in U (see Figure 13(a)). Thus, the arc (x1,w1)(x_1,w_1) is contained in the copy (u′,u,x1,y1,z1,w1)(u',u,x_1,y_1,z_1,w_1) of T1(2,1,2)T_1(2,1,2).

Three diagrams showing the use of WAU to complete the proof

Figure 13. Using WAU to complete the proof. Dashed lines correspond to non-edges.

Since T1(2,1,2)T_1(2,1,2) is WAU due to Lemma 5.1, this arc should be an arc corresponding to the arc (d,a)(d,a) (see Figure 8(a)) in a copy B=(s1,s2,w1,s3,s4,x1)B=(s_1,s_2,w_1,s_3,s_4,x_1) of T1(2,1,2)T_1(2,1,2) in GG. Since w1∈R′w_1 \in R', neither of s2s_2 and s3s_3 belongs to UU. If both s2,s3∉V(A)s_2,s_3 \notin V(A), then BB is contained in G[R]G[R]. Due to the hitting condition, we infer that {x2,y1,y2}⊆{s1,s4}\{x_2,y_1,y_2\} \subseteq\{s_1,s_4\}, which is impossible. Thus, at least one of the vertices s2,s3s_2,s_3 should be in V(A)V(A).

By symmetry, we may assume that s3∈V(A)s_3 \in V(A). A direct case analysis shows that s3=x2s_3=x_2, since in all other cases we are able to detect a vertex w∈NG(U)w \in N_G(U) and a copy of T1(2,1,2)T_1(2,1,2) contained in RwR_w, in contradiction with the hitting condition, see Figure 13(b):

  • s3=y1s_3=y_1: Rx1R_{x_1} contains the copy (w1,y1,z1,y2,x2,z2)(w_1,y_1,z_1,y_2,x_2,z_2);

  • s3=z1s_3=z_1: Ry1R_{y_1} contains the copy (x1,w1,z1,y2,x2,z2)(x_1,w_1,z_1,y_2,x_2,z_2);

  • s3=z2s_3=z_2: Rx1R_{x_1} contains the copy (w1,z2,z1,y2,x2,y1)(w_1,z_2,z_1,y_2,x_2,y_1);

s3=y2s_3 = y_2: Ry1R_{y_1} contains the copy (z2,z1,y2,w1,x1,x2)(z_2, z_1, y_2, w_1, x_1, x_2).

This implies that s2∈R′s_2 \in R', since otherwise s2∈V(A)s_2 \in V(A), and a symmetric analysis as the one above shows that s2=x2s_2 = x_2, implying s2=s3s_2 = s_3, which is impossible. For all possible variants of placement the vertex s1s_1 we now come to a contradiction with the hitting condition. The case analysis is similar to the previous one, see Figure 13(c):

s1∈R′∪{z1,z2}s_1 \in R' \cup\{z_1,z_2\}: Ry1R_{y_1} contains the copy (s1,s2,w1,x2,y2,x1)(s_1, s_2, w_1, x_2, y_2, x_1);

s1=y1s_1 = y_1: Ry2R_{y_2} contains the copy (w1,s2,y1,z1,z2,x1)(w_1, s_2, y_1, z_1, z_2, x_1);

s1=y2s_1 = y_2: Rx1R_{x_1} contains the copy (w1,s2,y2,z1,z2,x2)(w_1, s_2, y_2, z_1, z_2, x_2).

We have analyzed all possible cases and come to a contradiction in each of them. This completes the proof.

Disconnected inherent graphs

Let H+H′H + H' denote the disjoint union of graphs HH and H′H'. It seems to us that the following natural statement is true.

Conjecture 6.1. Let (H,s,t)(H,s,t) be a two-rooted graph, and let H′H' be any graph. Then, the two-rooted graph (H+H′,s,t)(H + H',s,t) is inherent if and only if so is (H,s,t)(H,s,t).

The backward direction of the Conjecture 6.1 holds due to [11], where the authors proved the statement for the induced case. The same proof, with some obvious necessary modifications, remains valid for the NNI setting. In this case, the following analogue of [11 Proposition 5.8] holds. We include the proof for completeness.

Proposition 6.2. Let (H,s,t)(H,s,t) be an inherent two-rooted graph and let H′H' be any graph. Then the two-rooted graph (H+H′,s,t)(H + H',s,t) is inherent.

Proof. Let GG be a graph containing H+H′H + H' as a subgraph. Fix a copy ⟨H+H′⟩\langle H + H' \rangle of H+H′H + H' in GG, let ⟨H⟩\langle H \rangle and ⟨H′⟩\langle H' \rangle be the corresponding copies of HH and H′H', and let XX be the set of vertices of ⟨H′⟩\langle H' \rangle. Observe that ⟨H⟩\langle H \rangle is a subgraph of G−XG - X isomorphic to HH. Thus, since (H,s,t)(H,s,t) is inherent, G−XG - X contains an avoidable copy (⟨H1⟩,⟨s1⟩,⟨t1⟩)(\langle H_1\rangle,\langle s_1\rangle,\langle t_1\rangle) of (H,s,t)(H,s,t). Then, it can be verified that (⟨H1⟩∪⟨H′⟩,⟨s1⟩,⟨t1⟩)(\langle H_1\rangle\cup\langle H'\rangle,\langle s_1\rangle,\langle t_1\rangle) is an avoidable copy of (H+H′,s,t)(H + H',s,t) in GG. Thus, (H+H′,s,t)(H + H',s,t) is inherent.

There is a natural way of how one could attempt to prove the forward direction of Conjecture 6.1. Suppose that s,t∈V(H)s,t \in V(H) and (H+H′,s,t)(H + H',s,t) is inherent. To show that (H,s,t)(H,s,t) is inherent, consider an arbitrary graph GG containing HH as a subgraph. Let G′G' be the disjoint union of GG and H′H'. Then, G′G' contains a copy of H+H′H + H'. Since (H+H′,s,t)(H + H',s,t) is inherent, G′G' also contains an avoidable copy (⟨H+H′⟩,⟨s⟩,⟨t⟩)(\langle H + H'\rangle,\langle s\rangle,\langle t\rangle) of (H+H′,s,t)(H + H',s,t) in G′G'. This, however, does not necessarily imply that (⟨H⟩,⟨s⟩,⟨t⟩)(\langle H\rangle,\langle s\rangle,\langle t\rangle) is an avoidable copy of (H,s,t)(H,s,t) in GG, as illustrated by the following example. Suppose that H≅H′≅K3H \cong H' \cong K_3, with ss and tt adjacent, and let GG be the graph obtained from K3K_3 by adding a pendant edge to each vertex. Then, there is a simplicial copy of H+H′H + H' in G+K3G + K_3, even though GG contains a copy of HH but no avoidable copy of (H,s,t)(H,s,t).

We point out that there are inherent two-rooted graphs (H,s,t)(H,s,t) such that ss and tt are in different connected components. The following proposition provides an example.

Proposition 6.3. Let H=PkH = P_k, k>1k > 1, and (H,s,t)(H,s,t) be the endpoint-rooted path, which is inherent. Let H′H' be the graph obtained from HH by removing the edge incident with ss (thus, leaving ss isolated). Then (H′,s,t)(H',s,t) is inherent.

Proof. Let GG be a graph containing H′H' as a subgraph. Suppose first that GG contains PkP_k as a subgraph. Since (H,s,t)(H,s,t) is inherent, GG contains an avoidable copy (⟨H⟩,⟨s⟩,⟨t⟩)(\langle H\rangle,\langle s\rangle,\langle t\rangle) of (H,s,t)(H,s,t). The copy of (H′,s,t)(H',s,t) obtained by deleting from (⟨H⟩,⟨s⟩,⟨t⟩)(\langle H\rangle,\langle s\rangle,\langle t\rangle) the unique edge incident with ⟨s⟩\langle s\rangle is an avoidable copy of (H′,s,t)(H',s,t) because the deleted edge can not be used by any extension.

Suppose now that GG does not contain PkP_k as a subgraph. Then every copy of (H′,s,t)(H',s,t) is simplicial in GG since an extension of such a copy gives a subgraph isomorphic to PkP_k.

We conjecture the following generalization of Proposition 6.3.

Conjecture 6.4. Let (H,s,t)(H,s,t) be a two-rooted inherent graph such that s≠ts \ne t, dH(s)=1d_H(s) = 1, and let H′H' be obtained from HH by deleting the unique edge incident with ss. Then (H′,s,t)(H',s,t) is inherent.

Note that if HH is connected, the fact that ss is a pendant vertex is a consequence of the NCI property (recall Observation 1.2).

Confining results

In this section we present two main techniques for constructing confining graphs, which are used to prove that a two-rooted graph is not inherent.

Confining by bipartite graphs

We first demonstrate how to use complete bipartite graphs to confine trees with imbalanced color classes. Recall that for any inherent connected two-rooted graph (H,s,t)(H,s,t), the graph HH is a tree and any tree can be properly colored with two colors.

Theorem 7.1. Let (H,s,t)(H,s,t) be a connected inherent two-rooted graph such that HH is a tree with color classes CC, C‾\overline{C}, and assume that s,t∈Cs,t \in C. Then ∣C‾∣≤∣C∣≤∣C‾∣+1|\overline{C}| \le|C| \le|\overline{C}|+1.

Proof. Suppose that the chain of inequalities ∣C‾∣≤∣C∣≤∣C‾∣+1|\overline{C}| \le|C| \le|\overline{C}|+1 does not hold. In this case, we show that (H,s,t)(H,s,t) is confined by the complete bipartite graph Kn,mK_{n,m}, where n=∣C∣n=|C|, m=∣C‾∣+2m=|\overline{C}|+2. We prove this statement by considering two cases.

Case 1: ∣C∣≥∣C‾∣+2|C| \ge|\overline{C}|+2. Note that for every copy (⟨H⟩,⟨s⟩,⟨t⟩)(\langle H\rangle,\langle s\rangle,\langle t\rangle) of (H,s,t)(H,s,t) in Kn,mK_{n,m}, vertices of the same color class are in the same part of Kn,mK_{n,m}. Hence, ⟨s⟩\langle s\rangle and ⟨t⟩\langle t\rangle are in the same part and all vertices of this part are vertices of the copy (⟨H⟩,⟨s⟩,⟨t⟩)(\langle H\rangle,\langle s\rangle,\langle t\rangle). Therefore we have two free vertices in the other part and the copy can be extended. But this extension can not be closed for obvious reasons.

Case 2: ∣C∣<∣C‾∣|C| < |\overline{C}|. Again, for every copy of HH in Kn,mK_{n,m}, vertices of the same color class are in the same part of Kn,mK_{n,m}. In particular, ⟨s⟩\langle s\rangle and ⟨t⟩\langle t\rangle are in the same part. This part should have nn vertices, because otherwise it should contain all vertices of the color class C‾\overline{C}, but ∣C‾∣>n|\overline{C}|>n. Therefore, we have two free vertices in the other part and the copy can be extended. But this extension can not be closed for obvious reasons.

Let us note that the assumption that s,t∈Cs,t \in C in Theorem 7.1 is not necessary. For example, in an inherent path T1(l,0,l′)T_1(l,0,l') where l≥2l \ge2 is even and l′≥0l' \ge0, the distance between the roots is odd, hence, they cannot both belong to CC.

Confining by path augmentation

An alternative way to confine a two-rooted graph is to add paths to it. This technique will be used to construct confining graphs for several families, including leaf-extended trees, combs of type II, and rakes. Before formulating results of this type we need the following additional concept.

Definition 7.2. A tree is called leaf-extended if it can be obtained from a subcubic tree in which every neighbor of every leaf is of degree 3, by subdividing each pendant edge kk times, for some fixed k≥1k \ge1 (see, e.g., Figure 14, where k=1k=1).

Figure 14. A leaf-extended tree (to the right) obtained from a tree (to the left) by subdividing pendant edges, k=1k = 1.

Proposition 7.3. Let HH be a leaf-extended tree, ss be a pendant vertex of HH, and let tt be adjacent to a pendant vertex distinct from ss. Then (H,s,t)(H,s,t) can be confined.

Proof. Let HH be a leaf-extended tree obtained from a subcubic tree TT in which every neighbor of every leaf is of degree 3 by subdividing each pendant edge kk times. We construct the confining graph GG of (H,s,t)(H,s,t) by adding paths of length 2 through new vertices between each pendant vertex and its neighbor (see Figure 15). Let (⟨H⟩,⟨s⟩,⟨t⟩)(\langle H\rangle,\langle s\rangle,\langle t\rangle) be a copy of (H,s,t)(H,s,t) in GG. We claim that from each pair of vertices of degree 2 in each triangle of GG, exactly one of these two vertices belongs to ⟨H⟩\langle H\rangle. Indeed, there cannot be more than one such vertex, since each pendant vertex of a leaf-extended tree is at distance k+1k+1 from a vertex of degree 3. Moreover, by a counting argument applied to all such pairs, we infer that there must be exactly one. This means that each copy of (H,s,t)(H,s,t) has a (unique) extension in GG, but these extensions are not closable since the roots are in different triangles.

Figure 15. A confining graph of the leaf-extended tree from Figure 14. Up to automorphism, the graph admits only one copy of the leaf-extended tree, which is not avoidable, since the two roots ss and tt (marked by white circles) are not adjacent, thus showing confinement in this case.

Note that for a leaf-extended tree shown in Figure 15 the distance between the roots is 3. Thus Theorem 7.1 cannot be applied to this two-rooted graph.

Remark 7.4. The proof of Proposition 7.3 can be adjusted to the induced case as well. However, the confining graphs differ. They are obtained from a leaf-extended tree by adding paths of length 3 between pendant vertices and their neighbors.

In [11] it was shown that, for the induced setting, two-rooted combs of type II, rakes, and split rakes can be confined by adding paths to the graph HH9. A similar construction works also for the NNI setting.

Proposition 7.5. All two-rooted combs of type II can be confined.

Proof. Consider T2(p,q)T_2(p,q), a two-rooted comb of type II, with p,q≥1p,q \ge1. If p=1p=1, both roots have degree 1, so T2(p,q)T_2(p,q) does not satisfy the NCI property and is, hence, not inherent, by Observation 1.2. If p≥2p \ge2, add two additional paths of length 2 and identify their endpoints with pairs (a1,ap)(a_1,a_p) and (ap+q+1,a2p+q)(a_{p+q+1},a_{2p+q}), respectively (see Figure 16).

Note that in some cases Proposition 7.5 follows from Theorem 7.1. However, for some combs of type II the assumptions of Theorem 7.1 fail; in particular, whenever p+qp+q is odd, the distance between roots in T2(p,q)T_2(p,q) is odd.

Two-rooted rakes and two-rooted split rakes are confined by similar constructions, shown on Figure 17.

Again, in some cases the confining of rakes follows from Theorem 7.1, but in some cases the assumptions of Theorem 7.1 fail; in particular, whenever qq is odd, the distance between roots in T4(q)T_4(q) and T5(q)T_5(q) is odd.

Conclusion and Open Questions

In this paper, we extended the study of inherent two-rooted graphs from the induced to the more general not necessarily induced (NNI) setting. We developed a new proof technique focused around the CCS (Complementary Connected or Simplicial) property, which is a powerful sufficient condition for inherence. Using this framework, we showed that the Necessary Condition for Inherence (NCI) is also sufficient for all two-rooted paths and forks. To complement these positive results, we introduced two methods for proving non-inherence: confinement by bipartite graphs with imbalanced partitions and confinement by path augmentation, which we used to rule out several classes of trees.

This work opens several avenues for future research. In [9], the concept of shifting was used to prove inherence of paths in the induced setting. Shifting guarantees that any copy can be transformed into an avoidable one through a series of local modifications.

Question 8.1. Can our inherence results for paths and forks (Theorems 3.1 and 4.1) be strengthened to shifting-type results in the NNI setting?

A central question is the computational complexity of recognizing inherence. Note that PE-inherence is decidable due to Rabin’s theorem about decidability of monadic second-order theory for trees [14].

Question 8.2. Is the problem of deciding whether a given two-rooted graph is inherent decidable? If so, what is its complexity?

The CCS property is a sufficient condition for inherence. It would be interesting to know if it is also necessary.

Question 8.3. Does there exist an inherent two-rooted tree that is not a CCS graph?

Finally, this work lays the groundwork for a broader classification of inherent graphs.

Question 8.4. Beyond paths, can we find other families of two-rooted trees whose inherence is characterized by the NCI property?

Question 8.5. Is there a more general theory of confinement that applies to a wider range of graph structures? For example, one can consider more than two roots; for the case of PE-inherence, the first step in this direction was made in [10].

Another open question concerns a relation between the induced and NNI settings. It is clear that an induced copy of a two-rooted graph is an NNI copy also, but not necessarily the other way around. The same holds for extensions. Hence, the corresponding two variants of avoidability are incomparable. Remark 3.2 shows that some two-rooted graphs are inherent in the NNI setting but not in the induced one.

Question 8.6. Is there a two-rooted graph that is inherent in the induced setting but is not inherent in the NNI setting?

Appendix

A Dictionary of abbreviations

For convenience of the reader, we collect here a list of abbreviations of various properties used in this paper. All these properties apply to a two-rooted graph H=(H,s,t)\mathcal{H}=(H,s,t), except for the HH-CC property, which depends on a graph HH and applies to a graph GG.

AS: Arc Separating. In any H\mathcal{H}-smooth graph G=(V,E)G=(V,E) and any arc e=(x,y)∈Ee=(x,y)\in E such that ee is contained in a copy of HH in GG there exists a copy of HH that contains xx and does not contain yy (see Definition 2.2).

AU: Arc Universal. In any H\mathcal{H}-smooth graph GG, any arc of GG plays a role of each arc of HH (see Definition 2.2).

CCS: every H\mathcal{H}-smooth graph has the HH-CC property (see Definition 2.10).

EM: Extension Movable. The extension graph of H\mathcal{H} contains more than one copy of HH (see Definition 2.5).

HH-CC property (of a graph GG): there exists a copy H′H' of HH in GG such that G−V(H′)G-V(H') is connected (see Definition 2.9).

HCS: H-Component is Small. See Definition 2.13.

NCI: Necessary Condition for Inherence. The graph HH is either a path or a tree with maximum degree 3 such that ss is a pendant vertex and tt either coincides with ss or has degree 2 (see Definition 1.1).

VU: Vertex Universal. In any H\mathcal{H}-smooth graph GG, any vertex of GG plays a role of each vertex of HH (see Definition 2.2).

WAU: Weakly Arc Universal. In any H\mathcal{H}-smooth graph GG, any arc of GG contained in a copy of HH in GG plays a role of each arc of HH (see Definition 2.2).

WVU: Weakly Vertex Universal. In any H\mathcal{H}-smooth graph GG, any vertex of GG contained in a copy of HH in GG plays a role of each vertex of HH (see Definition 2.2).

Two-rooted graphs with n=4,5,6n=4,5,6 vertices

As shown in Theorem 3.1, all NCI two-rooted paths are inherent. Here we list small trees that are not covered by these general results. In particular, HH should have vertices of degree 3.

n=4n=4

The only 4-vertex tree that is not a path is the star K1,3K_{1,3}. The only possible placement of root for an inherent K1,3K_{1,3} satisfying the NCI property is a double root in a pendant vertex. But this two-rooted graph is not inherent. It is confined by a bipartite graph. In terms of Theorem 7.1 ∣C∣=3|C|=3, ∣Cˉ∣=1<∣C∣−1|\bar{C}|=1<|C|-1. Hence, the graph is not inherent due to Theorem 7.1.

n=5n=5

Each subcubic tree on 5 vertices that is not a path can be obtained from a subcubic tree on 4 vertices by attaching a pendant edge to a vertex of degree at most 2. There exists a unique such tree on 5 vertices, namely, the fork graph.

To determine the number of NCI two-rooted forks up to isomorphism, note that there are two orbits of fork automorphisms on pendant vertices and only one vertex of degree 2. Thus, the number of two-rooted graphs in the list is 2+2=42+2=4. The corresponding two-rooted forks are shown in Figure 18.

Figure 18. All the 5-vertex two-rooted graphs satisfying the NCI property. Roots are shown as white circles. If only one root is shown, it means that the root is double, that is, s=ts=t. The labels under the graphs read “not inherent” and “all these are PE-forks and they are inherent by Theorem 4.1”.

The first two-rooted fork in Figure 18 is confined by the graph shown in Figure 19. Hence, it is not PE-inherent. Up to automorphism, there is only one copy of the two-rooted fork in the graph, and this copy is not avoidable.

Figure 19. Confining graph for the non-inherent two-rooted fork in Figure 18.

n=6n=6

Each subcubic tree on 6 vertices that is not a path can be obtained from a subcubic tree on 5 vertices by attaching a pendant edge to a vertex of degree at most 2. Up to isomorphism, this results in three trees, see Figure 20. We provide their names in our tree naming system.

Three 6-vertex non-path trees labelled $F(2,1,2)$, $F(1,1,3)$, and $F(1,2,1)$

Figure 20. 6-vertex non-path trees that up to isomorphism.

There are five two-rooted graphs on the graph F(2,1,2)F(2,1,2) satisfying the NCI property. Indeed, there are two different pendant vertices up to automorphism and two vertices of degree 2. For an endpoint of path P5P_5 the two vertices of degree 2 differ, while for a third pendant vertex they are the same up to automorphism of one-rooted graph. These two-rooted graphs, along with their names, are shown in Figure 21.

Figure 21. Two-rooted graphs (H,s,t)(H,s,t) with H=F(2,1,2)H=F(2,1,2) satisfying the NCI property. Among them, only T1(2,1,2)T_1(2,1,2) is inherent.

For a proof that T1(2,1,2)T_1(2,1,2) is inherent, see § 5. From Proposition 7.5 we conclude that T2(2,1)T_2(2,1) is not inherent. The leftmost two-rooted graph in the first row of Figure 21 is non-standard for our naming conventions; we denote it as Ta(2,1,2)T_a(2,1,2). It is confined by the graph shown in Figure 24(a). In this graph, the only vertex of degree 3 that is an endpoint of two edge-disjoint paths of length 2 is the central vertex. Hence, there are exactly two copies of Ta(2,1,2)T_a(2,1,2) in the graph and neither of them is avoidable.

Confining graphs for the two-rooted graphs mentioned in the text.

Figure 24. Confining graphs for the two-rooted graphs mentioned in the text.

The two graphs in the second row of Figure 21 are not inherent. They are both confined by the graph shown in Figure 24(b). In this graph, there is a unique path of length 4 up to automorphism. Consequently, up to automorphism, there is only one copy of Tb(2,1,2)T_b(2,1,2) in the graph, and this copy is not avoidable. Similar observations apply to Tc(2,1,2)T_c(2,1,2).

There are six two-rooted graphs on the graph F(1,1,3)F(1,1,3) satisfying the NCI property. Indeed, up to automorphism, there are two different pendant vertices and two vertices of degree 2. Each pendant vertex gives three variants. All variants are shown in Figure 22. It turns out that none of these two-rooted graphs is inherent.

Figure 22. Two-rooted graphs (H,s,t)(H,s,t) with H=F(1,1,3)H=F(1,1,3) satisfying the necessary condition. None of these two-rooted graphs is inherent.

Graphs Ta(1,1,3)T_a(1,1,3), Ta(3,1,1)T_a(3,1,1), Tc(3,1,1)T_c(3,1,1), and T1(3,1,1)T_1(3,1,1) are not inherent, since Theorem 7.1 is applied for them: distance between roots is even. For these graphs we have ∣C∣=4|C|=4, ∣C‾∣=2|\overline{C}|=2, and inequalities in Theorem 7.1 are violated. A graph confining Td(3,1,1)T_d(3,1,1) and Te(3,1,1)T_e(3,1,1) is shown in Figure 24(c). Up to automorphism, there is a unique copy of Td(3,1,1)T_d(3,1,1) in this graph and that copy is not avoidable. The same holds for Te(3,1,1)T_e(3,1,1).

Since F(1,2,1)F(1,2,1) has no vertices of degree 2 and its pendant vertices form an orbit of the automorphism group, there is exactly one two-rooted graph on the graph F(1,2,1)F(1,2,1) satisfying the necessary condition. It is T1(1,2,1)T_1(1,2,1) (see Figure 23). This two-rooted graph is not inherent, since it is confined by Petersen graph, see Figure 24(d). Similarly to most cases considered before, up to automorphism, there is only one copy of T1(1,2,1)T_1(1,2,1). It is easy to verify using Figure 24(d) that this copy is not avoidable.

Figure 23. The only two-rooted graph (H,s,t)(H,s,t) with H=F(1,2,1)H=F(1,2,1) satisfying the necessary condition is T1(1,2,1)T_1(1,2,1). It is not inherent.

References

  1. [1]Jesse Beisegel, Maria Chudnovsky, Vladimir Gurvich, Martin Milanič, and Mary Servatius. Avoidable vertices and edges in graphs. In Zachary Friggstad, Jörg-Rüdiger Sack, and Mohammad R. Salavatipour, editors, Algorithms and Data Structures - 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5-7, 2019, Proceedings, volume 11646 of Lecture Notes in Computer Science, pages 126–139. Springer, 2019.arxiv.org/abs/1907.12078
  2. [2]Jesse Beisegel, Maria Chudnovsky, Vladimir Gurvich, Martin Milanič, and Mary Servatius. Avoidable vertices and edges in graphs: Existence, characterization, and applications. Discrete Appl. Math., 309:285–300, 2022.DOI
  3. [3]Anne Berry, Jean R. S. Blair, Pinar Heggernes, and Barry W. Peyton. Maximum cardinality search for computing minimal triangulations of graphs. Algorithmica, 39(4):287–298, 2004.DOI
  4. [4]Anne Berry, Jean-Paul Bordat, Pinar Heggernes, Geneviève Simonet, and Yngve Villanger. A wide-range algorithm for minimal triangulation from an arbitrary ordering. J. Algorithms, 58(1):33–66, 2006.
  5. [5]Marthe Bonamy, Oscar Defrain, Meike Hatzel, and Jocelyn Thiebaut. Avoidable paths in graphs. Electron. J. Combin., 27(4):Paper No. 4.46, 9, 2020.arxiv.org/abs/1908.03788
  6. [6]Vašek Chvátal, Irena Rusu, and R. Sritharan. Dirac-type characterizations of graphs without long chordless cycles. Discrete Math., 256(1-2):445–448, 2002.DOI
  7. [7]Reinhard Diestel. Graph theory, volume 173 of Graduate Texts in Mathematics. Springer, Berlin, sixth edition, 2025.
  8. [8]G. A. Dirac. On rigid circuit graphs. Abh. Math. Sem. Univ. Hamburg, 25:71–76, 1961.DOI
  9. [9]Vladimir Gurvich, Matjaž Krnc, Martin Milanič, and Mikhail Vyalyi. Shifting paths to avoidable ones. J. Graph Theory, 100(1):69–83, 2022.arxiv.org/abs/2008.01128
  10. [10]Vladimir Gurvich, Matjaž Krnc, and Mikhail Vyalyi. Growing trees and amoebas’ replications. Results Math., 80(4):Paper No. 117, 17, 2025.arxiv.org/abs/2401.07484
  11. [11]Vladimir Gurvich, Matjaž Krnc, Martin Milanič, and Mikhail Vyalyi. Avoidability beyond paths. Electron. J. Combin., 32(2):Paper No. 2.27, 39, 2025.arxiv.org/abs/2208.12803
  12. [12]Pinar Heggernes. Minimal triangulations of graphs: a survey. Discrete Math., 306(3):297–317, 2006.
  13. [13]Tatsuo Ohtsuki, Lap Kit Cheung, and Toshio Fujisawa. Minimal triangulation of a graph and optimal pivoting order in a sparse matrix. J. Math. Anal. Appl., 54(3):622–633, 1976.DOI
  14. [14]Michael O. Rabin. Decidability of second-order theories and automata on infinite trees. Trans. Amer. Math. Soc., 141:1–35, 1969.

Paper details

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

views · 0

downloads · 0

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

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents