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 -vertex path must also contain an avoidable -vertex path and proved the claim for . 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 . 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 consists of a graph with two specified vertices and , called roots.
This framework formalizes the notion of an extension for arbitrary structures: an extension of an induced copy of in a larger graph is an induced subgraph obtained by adding to the copy of a pair of pendant edges incident with the copies of and , respectively. Such an extension is closable if a path exists in between these new pendant vertices, using only vertices outside the closed neighborhood of the original copy. A copy of 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 must also contain an avoidable induced copy of .{^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 is said to have NCI property if:
either is a path with an endpoint ,
or is a tree with maximum degree 3 such that , with if and only if .
In particular, a two-rooted graph can only have the NCI property if it is a two-rooted tree, that is, 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 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 to be avoidable in a graph 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 . 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 , depicted in Figure 8(a) and formally defined in § 1.2.
Figure 8. (a) is a copy of ; (b) Names of the arcs of
Theorem 1.5. 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 in a graph is a subgraph of isomorphic to . A subgraph embedding of a graph in a graph is an injection that maps adjacent vertices to adjacent vertices. The path graph on vertices is denoted by . For other standard graph theory notation we refer the reader to Diestel [7].
A two-rooted graph is a triple such that is a graph and and are two (not necessarily distinct) vertices of which we call roots. We will denote two-rooted graphs in calligraphic font, such as . For convenience and without loss of generality, we always assume for a two-rooted graph that .
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 and a two-rooted graph , a copy of in is any two-rooted graph such that is a subgraph of for which there exists an isomorphism of to mapping to and to .
Given a two-rooted graph , the extension graph of is the graph obtained from by adding to it two pendant edges and ; the corresponding two-rooted graph is said to be an extension of . Given a graph , a two-rooted graph , and a copy of it in , an extension of in is any extension of such that is a subgraph of . In particular, , vertices and are distinct, the graph obtained from by deleting and is , and and are unique neighbors of and in , respectively. Furthermore, we say that an extension of in is closable if there exists an -path in having no vertex in common with .
Definition 1.6. Let be a copy of a two-rooted graph in a graph . We say that is avoidable (in ) if all extensions of in are closable.
In particular, a copy of in that has no extensions is trivially avoidable. Such a copy will be called simplicial.
Remark 1.7. If is a path and and are its endpoints, the above definitions of an extension of a copy of in a graph , 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 .
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 is inherent if every graph that contains a copy of also contains an avoidable copy of .
The following concept provides a natural certificate of non-inherence.
Definition 1.9. Given a two-rooted graph and a graph , we say that confines (or: is a confining graph for ) if contains a copy of but no avoidable copy of .
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 consists of a path and pending edges added to vertices .
Two-rooted combs of type I are the two-rooted graphs , where and (see Figure 2 and Figure 4 for two examples, namely and , respectively). Note that is a two-rooted path and is an endpoint-rooted path.
Figure 2. is a copy of the two-rooted fork .
Figure 4. is a copy of the two-rooted fork .
Two-rooted combs of type II are the two-rooted graphs , (see Figure 16 for an example, namely ).
Figure 16. Up to automorphism, the graph admits only one copy of , which is clearly not avoidable, thus showing that is confined.
Two-rooted combs of type III are the two-rooted graphs
and (see Figure 3 for an example, namely ).
Figure 3. is a copy of the two-rooted fork .
For an integer we denote by the two-rooted graph obtained from the two-rooted comb of type II by subdividing each edge of the form , . Any two-rooted graph equivalent to , for some , will be referred to as a two-rooted rake (see Figure 17(a) for an example, namely ).
Figure 17. Up to automorphism, the graph on the left admits only one copy of , while the graph on the right admits only one copy of . Clearly, neither of these copies is avoidable, hence, the two-rooted graphs and are confined.
For an integer we denote by the two-rooted graph obtained from the two-rooted comb of type II by subdividing each edge of the form , , and adding a pendant edge to each vertex of degree two joining and for all . Any two-rooted graph equivalent to , for some , will be referred to as a two-rooted split rake (see Figure 17(b) for an example, namely ).
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 be a two-rooted graph. A graph is -smooth if is connected, contains a copy of , and there are no simplicial copies of in .
Due to Observation 1.2 we are mainly concerned in -smooth graphs for the case when has the NCI property.
In many cases -smoothness implies that there are many copies of . We introduce several concepts capturing this ‘richness’ of copies of a two-rooted graph. Recall that a subgraph embedding of a graph in a graph is an injection that maps adjacent vertices to adjacent vertices.
Definition 2.2. A two-rooted graph is said to be
VU (Vertex Universal) if for any -smooth graph , any , and any , there exists a subgraph embedding of in such that ;
WVU (Weakly Vertex Universal) if for any -smooth graph , any contained in a copy of in , and any , there exists a subgraph embedding of in such that ;
AU (Arc Universal) if for any -smooth graph , any arc , and any arc , there exists a subgraph embedding of in such that and ;
WAU (Weakly Arc Universal) if for any -smooth graph , any arc contained in a copy of in , and any arc , there exists a subgraph embedding of in such that and ;
AS (Arc Separating) if for any -smooth graph and any arc such that is contained in a copy of in $G there exists a copy of that contains and does not contain .
For a VU graph , each vertex in an -smooth graph is contained in a copy of such that corresponds to a vertex of the maximal degree in . So, the following corollary is immediate.
Corollary 2.3. Let be VU and let be -smooth. Then .
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 with , WVU implies VU.
Proof. Let be the union of vertex sets of all copies of in an -smooth graph . Then, . Let be an edge such that . Since is WVU, there exists a subgraph embedding such that is a neighbor of a pendant vertex in . If is contained in , then . Otherwise, substituting by we get another copy of in and this copy contains . Therefore . So, in any case. Thus, since is connected. This implies that 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 is EM (Extension Movable) if the extension graph of contains more than one copy of .
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 is EM and WAU, then is AS.
Proof. Let be a -smooth graph and let be an arc of that is contained in a copy of in . Since is EM, in the extension graph of we can choose a copy of different from . Furthermore, we can choose an arc of such that and . Such an arc does exist, since is connected, any edge in is pendant, thus, any path in from a vertex in to a vertex in has an arc that of such that and . Since is WAU, there exists a copy of in such that corresponds to and corresponds to . Since is -smooth, has an extension in . Choose in the extension graph a copy of such that and . □
In verifying WAU for a two-rooted graph , it is helpful to use the following equivalence relation on the set of arcs of .
Definition 2.7. For graphs and , two arcs and of are -equivalent if there are two subgraph embeddings of in such that . We denote this relation as .
For any two graphs and , the relation is an equivalence relation on the set of arcs of . 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 is WAU if for every -smooth graph , every two arcs of are -equivalent to each other.
Now we turn to an important property sufficient for the existence of an avoidable copy. Let be a copy of in a graph such that is connected. Then the copy is avoidable: every extension has endpoints in and they are connected by a path inside . Note that this property does not depend on roots.
Definition 2.9. Given two graphs and , the graph has the -Connected Complement property) (-CC property for short) if there exists a copy of in such that is connected.
Definition 2.10. A two-rooted graph is a CCS graph (Connected Complement or Simplicial) if every -smooth graph has the -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 be a graph. For a graph , a pair of subsets of is -avoiding if is a partition of , the subgraph of induced by is connected, and the subgraph of induced by contains a copy of . An -avoiding pair is called inclusion-maximal if no -avoiding pair satisfies .
For graphs and , an -avoiding pair in , and , we denote by the graph .7 Note that an inclusion-maximal -avoiding pair in a graph satisfies the hitting condition: if then contains no copies of . In other words, each copy of in contains . Otherwise, if is not covered by the copy, then the set can be extended by a vertex preserving the properties of an -avoiding pair. Later we will need the following property, which is a simple implication of the hitting condition.
Proposition 2.12. Let be a two-rooted tree, an inclusion-maximal -avoiding pair in a -smooth graph , and . Then has a neighbor in each component of .
Proof. Suppose for contradiction that for some component of .8 Since is connected, . Let . The hitting condition implies that there exists a copy of containing and . Let be a shortest path from to in . Then, all the vertices of except belong to , implying that , a contradiction.
Definition 2.13. A two-rooted graph is HCS (H-Component is Small) if for any -smooth graph and any inclusion-maximal -avoiding pair in , the following implication holds: if there exists a vertex such that is connected, then .
The HCS property implies the -CC property of any -smooth graph , since by definition the graph contains a copy of . The basic lemma for the proofs of inherence is as follows.
Lemma 2.14. If a two-rooted graph 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 -smooth graph and an inclusion-maximal -avoiding pair in .
We claim that for every vertex , every connected component of satisfies . We prove the claim by contradiction. Suppose that for some component of , where . Then, is a component in , since . It follows from Proposition 2.12 that there exists an edge such that . Since is AU, there exists a copy of in that contains the arc . Hence, as is AS, there is a copy of that contains and does not contain . This copy should be contained in since . Thus is an -avoiding pair, contradicting the maximality of .
For , let be the connected components of ordered non-increasingly by size, and let for all . Then . Choose such that the vector is maximal with respect to the lexicographic order. We claim that is connected. Since is HCS, this implies that -CC property of does hold and, consequently, that is CCS.
Now, we prove the claim. Suppose for contradiction that . By Proposition 2.12, has a neighbor in . Then, due to the maximality in the lexicographic order, since if , then the vector is lexicographically larger than (the component is enlarged by at least 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 , the following properties are equivalent.
(a) is inherent.
(b) satisfies the NCI property.
(c) is for some and .
(d) 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 is confined by the Petersen graph in the induced setting.
The implication holds for general connected two-rooted graphs (cf. Observation 1.2), while the implications and and are immediate consequences of the definitions. Hence, it remains to show that every two-rooted graph of the form , with and , is CCS. In subsequent analysis we denote the number of vertices by . In the case 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 . We prove the implication by showing that 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. is AS and AU.
Proof. The extension graph of contains a path . Thus it contains at least two paths . So, is EM.
Next, we prove that is WAU. For this purpose we fix a -smooth graph and use the -equivalence relation on arcs of . Let be the vertices of and , be its edges. Arcs of are and , .
Let be a copy of in a -smooth graph . Note that is also a copy of in . Since is -smooth, both endpoints , are roots of non-simplicial copies of , both of them have neighbors in , say , such that , for (it is possible that if ).
Looking at the path we see and for . So all are -equivalent as well as all . Now look at the copy of in . Comparing and shows that and . Thus every two arcs of are -equivalent to each other and, due to Lemma 2.8, is WAU and thus also WVU. Lemma 2.6 implies that is also AS.
To conclude the proof we now show that is AU. Since , by Lemma 2.4, is VU. Let be an -smooth graph, be an arc. By VU, there exists a copy of such that . We distinguish the following cases:
If , we are done.
If for some , the copy contains the arc .
Otherwise, the copy contains the arc .
So, in all cases the arc is in a copy of . Now AU follows from the fact that is WAU.
Lemma 3.4. is HCS.
Proof. Let be an -smooth graph, be an inclusion-maximal -avoiding pair in , and be a copy of in . Since is -smooth, both endpoints , of are roots of non-simplicial copies of , hence, both of them have neighbors outside of . We now show that either (in which case is an outer path) or (in which case is an inner path).
Suppose that and . An extension of a copy of gives an edge such that . We get a copy of in , a contradiction with the hitting condition. Similarly, we obtain a contradiction if and . Hence, either none of has a neighbor in or both of them have neighbors in . In the second case neither of has a neighbor in due to the same argument. Consequently, 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 has a neighbor in , then is outer, and if not, it is an inner path.
Assume that is an outer path, . To complete this case, let us prove by contradiction that (which is equivalent to ). Suppose that . Due to the hitting condition, there is no edge in connecting a vertex in with a vertex in . This implies that is a cut set in . Hence, there exists an edge such that and . Let be the smallest number satisfying this condition. Since is an outer path, . Choose as a longest path in starting at . Due to maximality of , : otherwise, the path contains a subpath with vertices that does not contain , which is impossible due to the hitting condition. Since , have neighbors in and is connected, there exists a cycle , where for all and , .
Take a copy of (indices in are taken modulo ). Furthermore, this copy is simplicial in : there are no edges from to due to the hitting condition, there are no edges from to , , by the choice of , for all the vertex belongs to since , and, finally, there are no edges from to since the path is a longest one. We get a contradiction, since has no simplicial copies of .
By the previous arguments, we may assume that all the copies of in are inner paths. To complete the proof, we verify that if there exists a vertex such that is connected, then . Fix such that is connected. Due to the hitting condition, is contained in every copy of in . Choose the minimal such that in a copy of in . Suppose that . Take an extension of a copy , where and are extension edges. If , then the path is outer, a contradiction. Otherwise, since , the copy of contains the vertex , moreover, this vertex corresponds to the -the vertex of the path, a contradiction with the definition of . Thus and . Similar arguments show that, since 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 (or, equivalently, ) is the unique 5-vertex tree with maximum degree 3. We denote a fork with vertex set and edge set by . 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 -fork is and .
Proof. In Figure 5(b-Figure 5d) the extension graphs for -forks are shown, together with the labels of vertices that we use in this proof.
It is easy to verify that -forks are : for an additional copy is, e.g., ; for an additional copy is, e.g., ; for an additional copy is, e.g., .

Figure 5. Naming arcs of the fork; and the extension graphs of PE-forks.
Next, we prove that is . For this purpose we use Lemma 2.8. So, we are going to prove that for every -smooth graph , all arcs of are -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 . Let and be a -smooth graph. The copy of shows that , , . Furthermore, the copy gives equivalences , , , . Hence, all arcs of are -equivalent:
We conclude from Lemma 2.8 that is .
Let and be a -smooth graph. The copy of shows that , , , see Figure 5(c). The copy shows that , . So, all arcs of are -equivalent:
From Lemma 2.8 we conclude that is .
Finally, we consider the case . This case is more complicated. Let be a -smooth graph. The copy from the extension graph in Figure 5(d) gives equivalences , . One more copy of in the extension graph gives the same equivalences. So, we take an extension of , which gives an edge , and a new copy . The copy gives equivalences , , . So, all arcs of are -equivalent:
and an application of Lemma 2.8 shows that 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 be a PE-fork and be an -smooth graph. Take an arc in . Since is WAU, it is WVU by a direct implication and VU by Lemma 2.4. Take a copy of containing . If the copy contains also , we are done, since is WAU. If not, there should be an edge in the copy. Since is WAU, this implies that there exists a copy of such that the arc 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 , we are done. If the copy does not contain , then substitute a pendant vertex adjacent to by , and we are also done. The remaining case is unique up to isomorphism, it is shown in Figure 6. In this case is an edge of the copy . Since is WAU, this completes
Figure 6. The special case in the proof of AU for a PE-fork.
the proof that 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 , a path , or a cycle for some .
Proof. Let be a connected fork-free graph with . If all vertices in have degree at most 2 then is path or a cycle, since is connected. From now on assume that there exists such that . We need to prove that (for ).
Suppose the contrary. Since is connected, there exists an edge , , . If , then, since has at least 5 vertices, we may assume that is chosen outside , and we obtain a copy of the fork, where with . If , then choose and get a copy of the fork. Thus, is not fork-free, a contradiction.
Lemma 4.4. A PE-fork is HCS.
Proof. Let be an -smooth graph, and be an inclusion-maximal -avoiding pair in , and such that is connected. Since is AU by Lemma 4.2, is also VU. Hence, by Corollary 2.3, we have .
We are going to prove that . So we need to exclude the case when . Note that in this case and is fork-free due to the hitting condition. From Lemma 4.3 we conclude that there are exactly three possible cases for .
Case , . Let be pendant vertices of the star . Then . This implies that for all , since there are only two possible edges in incident to : the edge , where is the center of the star and (possibly) the edge . Therefore . By the hitting condition, each copy of the fork in contains , and therefore is a fork. We come to a contradiction, since has an independent set of size 4 and the fork does not.
Case , . Enumerate vertices along the path: , where . Since , . Furthermore, since any copy of the fork should contain the set , the graph is fork-free and, since the fork has only 5 vertices, there exists a vertex in the path such that and therefore . Since and the path is induced, is not adjacent to at least one endpoint of the path. By symmetry, we may assume that . Notice that the connected component of the graph that contains the vertex satisfies , since contains all the vertices for , as well as vertex . Since has degree 3 in , we conclude that is neither a star, nor a path, nor a cycle. Since is fork-free, this contradicts Lemma 4.3.
Case , . Again, there exists a vertex in the cycle such that . Since , we conclude that . Enumerate vertices along the cycle starting from : , , where . For , in the connected component of the graph that contains the vertex , the vertex has degree at least 3 (due to the edges , , and ) and, moreover, , since contains at least four vertices of the cycle, as well as vertex . Since has degree at least 3 in , we conclude that is neither a star, nor a path, nor a cycle. By Lemma 4.3, contains a copy of the fork and, hence, so does . By the hitting condition, this implies that , hence, the only possible neighbors of in are , , and . Since also , we conclude that and, moreover, for . This leads to a contradiction with the fact that is -smooth, since a simplicial copy of does exist under these conditions, see Figure 7, where simplicial copies are shadowed.
Figure 7. Simplicial copies: for and for (on the left); for (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. is inherent.
The proof of Theorem 1.5 is similar to the proofs for PE-forks. In fact, we conjecture that 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 by a sequence of vertices in the order shown in Figure 8(a). For the purpose of analyzing -equivalence with respect to some -smooth graph , we name arcs of as shown in Figure 8(b). Due to automorphisms of , it is enough to consider only three pairs of arcs.
Lemma 5.1. is WAU.
Proof. Let be a -smooth graph. We fix a copy of in and an extension of it using edges and , as shown in Figure 9.
Figure 9. An extension of .
Let us compare the initial copy of and the copy in the extension graph. This gives equivalences , , , , . Thus, all arcs of are -equivalent:
and an application of Lemma 2.8 shows that is WAU.
Corollary 5.2. Let be a -smooth graph. Then .
Proof. Recall that WAU implies WVU. The corollary follows from Lemmas 2.4 and 5.1 and Corollary 2.3.
Lemma 5.3. Let be a -smooth graph. Then there exists an inclusion-maximal avoiding pair for in such that .
Proof. Take a copy of and its extension graph shown in Figure 9. The copy certifies that is an avoiding pair for in . It can be extended to an inclusion-maximal avoiding pair and the size of is at least 2 in that pair.
Proof of Theorem 1.5. Suppose for a contradiction that is not inherent. Then, there exists a connected confining graph for . In particular, the graph is -smooth. By Lemma 5.3, there exists an inclusion-maximal avoiding pair for in such that . Due to maximality of , the hitting condition holds: for each , the graph is -free.
Let (see Figure 8(a) for naming convention) be a copy of contained in . Since is a confining graph for , this copy of is not avoidable in ; hence, there exists a non-closable extension by edges . Let . Recall that is connected. So, if , then the extension is closable. Note that the case , is impossible because in this case does contain a copy of , in contradiction with the hitting condition. To complete the proof, we need to consider two remaining cases.
Case , . First, we note that , since otherwise we come to a contradiction with the hitting condition as explained above. From the hitting condition we also conclude that since the graphs and contain the copy of . Let be the edges of an extension of this copy. Note that it is possible that , and since . The copy of is contained in the graphs and , see Figure 10 (dashed circles in the figure indicate vertices that are in ). This implies that . Thus since this set is not empty (as is connected).
Figure 10. To the proof that .
The copy of is not avoidable. Due to the previous analysis and the fact that , there exists an extension of the copy by edges , where (see Figure 11). The copy is contained in and we come to a contradiction with the hitting condition.
Figure 11. A contradiction with the hitting condition.
Case , . The previous case shows that , holds for every copy of in . Take a copy and the ‘reflected’ copy . From extensions of these copies we conclude that .
Next step is to prove that . Suppose for contradiction that . Then an extension of the copy uses edges , such that (see Figure 12(a)). Thus the copy should not be contained in , implying that . If , then the copy is contained in , in contradiction with the hitting condition (see Figure 12(b)).
Figure 12. To the proof that .
If , then the copy is contained in (see Figure 12(c)). Again, we come to a contradiction. This shows that , as claimed.
Substituting by in the previous argument shows that as well.
Neighbors of in can coincide. In any case, since is connected and , there exists a path , where (see Figure 13(a)). Thus, the arc is contained in the copy of .

Figure 13. Using WAU to complete the proof. Dashed lines correspond to non-edges.
Since is WAU due to Lemma 5.1, this arc should be an arc corresponding to the arc (see Figure 8(a)) in a copy of in . Since , neither of and belongs to . If both , then is contained in . Due to the hitting condition, we infer that , which is impossible. Thus, at least one of the vertices should be in .
By symmetry, we may assume that . A direct case analysis shows that , since in all other cases we are able to detect a vertex and a copy of contained in , in contradiction with the hitting condition, see Figure 13(b):
: contains the copy ;
: contains the copy ;
: contains the copy ;
: contains the copy .
This implies that , since otherwise , and a symmetric analysis as the one above shows that , implying , which is impossible. For all possible variants of placement the vertex we now come to a contradiction with the hitting condition. The case analysis is similar to the previous one, see Figure 13(c):
: contains the copy ;
: contains the copy ;
: contains the copy .
We have analyzed all possible cases and come to a contradiction in each of them. This completes the proof.
Disconnected inherent graphs
Let denote the disjoint union of graphs and . It seems to us that the following natural statement is true.
Conjecture 6.1. Let be a two-rooted graph, and let be any graph. Then, the two-rooted graph is inherent if and only if so is .
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 be an inherent two-rooted graph and let be any graph. Then the two-rooted graph is inherent.
Proof. Let be a graph containing as a subgraph. Fix a copy of in , let and be the corresponding copies of and , and let be the set of vertices of . Observe that is a subgraph of isomorphic to . Thus, since is inherent, contains an avoidable copy of . Then, it can be verified that is an avoidable copy of in . Thus, is inherent.
There is a natural way of how one could attempt to prove the forward direction of Conjecture 6.1. Suppose that and is inherent. To show that is inherent, consider an arbitrary graph containing as a subgraph. Let be the disjoint union of and . Then, contains a copy of . Since is inherent, also contains an avoidable copy of in . This, however, does not necessarily imply that is an avoidable copy of in , as illustrated by the following example. Suppose that , with and adjacent, and let be the graph obtained from by adding a pendant edge to each vertex. Then, there is a simplicial copy of in , even though contains a copy of but no avoidable copy of .
We point out that there are inherent two-rooted graphs such that and are in different connected components. The following proposition provides an example.
Proposition 6.3. Let , , and be the endpoint-rooted path, which is inherent. Let be the graph obtained from by removing the edge incident with (thus, leaving isolated). Then is inherent.
Proof. Let be a graph containing as a subgraph. Suppose first that contains as a subgraph. Since is inherent, contains an avoidable copy of . The copy of obtained by deleting from the unique edge incident with is an avoidable copy of because the deleted edge can not be used by any extension.
Suppose now that does not contain as a subgraph. Then every copy of is simplicial in since an extension of such a copy gives a subgraph isomorphic to .
We conjecture the following generalization of Proposition 6.3.
Conjecture 6.4. Let be a two-rooted inherent graph such that , , and let be obtained from by deleting the unique edge incident with . Then is inherent.
Note that if is connected, the fact that 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 , the graph is a tree and any tree can be properly colored with two colors.
Theorem 7.1. Let be a connected inherent two-rooted graph such that is a tree with color classes , , and assume that . Then .
Proof. Suppose that the chain of inequalities does not hold. In this case, we show that is confined by the complete bipartite graph , where , . We prove this statement by considering two cases.
Case 1: . Note that for every copy of in , vertices of the same color class are in the same part of . Hence, and are in the same part and all vertices of this part are vertices of the copy . 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: . Again, for every copy of in , vertices of the same color class are in the same part of . In particular, and are in the same part. This part should have vertices, because otherwise it should contain all vertices of the color class , but . 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 in Theorem 7.1 is not necessary. For example, in an inherent path where is even and , the distance between the roots is odd, hence, they cannot both belong to .
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 times, for some fixed (see, e.g., Figure 14, where ).
Figure 14. A leaf-extended tree (to the right) obtained from a tree (to the left) by subdividing pendant edges, .
Proposition 7.3. Let be a leaf-extended tree, be a pendant vertex of , and let be adjacent to a pendant vertex distinct from . Then can be confined.
Proof. Let be a leaf-extended tree obtained from a subcubic tree in which every neighbor of every leaf is of degree 3 by subdividing each pendant edge times. We construct the confining graph of by adding paths of length 2 through new vertices between each pendant vertex and its neighbor (see Figure 15). Let be a copy of in . We claim that from each pair of vertices of degree 2 in each triangle of , exactly one of these two vertices belongs to . Indeed, there cannot be more than one such vertex, since each pendant vertex of a leaf-extended tree is at distance 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 has a (unique) extension in , 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 and (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 9. A similar construction works also for the NNI setting.
Proposition 7.5. All two-rooted combs of type II can be confined.
Proof. Consider , a two-rooted comb of type II, with . If , both roots have degree 1, so does not satisfy the NCI property and is, hence, not inherent, by Observation 1.2. If , add two additional paths of length 2 and identify their endpoints with pairs and , 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 is odd, the distance between roots in 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 is odd, the distance between roots in and 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 , except for the -CC property, which depends on a graph and applies to a graph .
AS: Arc Separating. In any -smooth graph and any arc such that is contained in a copy of in there exists a copy of that contains and does not contain (see Definition 2.2).
AU: Arc Universal. In any -smooth graph , any arc of plays a role of each arc of (see Definition 2.2).
CCS: every -smooth graph has the -CC property (see Definition 2.10).
EM: Extension Movable. The extension graph of contains more than one copy of (see Definition 2.5).
-CC property (of a graph ): there exists a copy of in such that is connected (see Definition 2.9).
HCS: H-Component is Small. See Definition 2.13.
NCI: Necessary Condition for Inherence. The graph is either a path or a tree with maximum degree 3 such that is a pendant vertex and either coincides with or has degree 2 (see Definition 1.1).
VU: Vertex Universal. In any -smooth graph , any vertex of plays a role of each vertex of (see Definition 2.2).
WAU: Weakly Arc Universal. In any -smooth graph , any arc of contained in a copy of in plays a role of each arc of (see Definition 2.2).
WVU: Weakly Vertex Universal. In any -smooth graph , any vertex of contained in a copy of in plays a role of each vertex of (see Definition 2.2).
Two-rooted graphs with 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, should have vertices of degree 3.
The only 4-vertex tree that is not a path is the star . The only possible placement of root for an inherent 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 , . Hence, the graph is not inherent due to Theorem 7.1.
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 . 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, . 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.
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.

Figure 20. 6-vertex non-path trees that up to isomorphism.
There are five two-rooted graphs on the graph 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 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 with satisfying the NCI property. Among them, only is inherent.
For a proof that is inherent, see § 5. From Proposition 7.5 we conclude that 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 . 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 in the graph and neither of them is avoidable.

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 in the graph, and this copy is not avoidable. Similar observations apply to .
There are six two-rooted graphs on the graph 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 with satisfying the necessary condition. None of these two-rooted graphs is inherent.
Graphs , , , and are not inherent, since Theorem 7.1 is applied for them: distance between roots is even. For these graphs we have , , and inequalities in Theorem 7.1 are violated. A graph confining and is shown in Figure 24(c). Up to automorphism, there is a unique copy of in this graph and that copy is not avoidable. The same holds for .
Since 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 satisfying the necessary condition. It is (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 . It is easy to verify using Figure 24(d) that this copy is not avoidable.
Figure 23. The only two-rooted graph with satisfying the necessary condition is . It is not inherent.
References
- [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]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]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]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]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]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]Reinhard Diestel. Graph theory, volume 173 of Graduate Texts in Mathematics. Springer, Berlin, sixth edition, 2025.
- [8]G. A. Dirac. On rigid circuit graphs. Abh. Math. Sem. Univ. Hamburg, 25:71–76, 1961.DOI
- [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]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]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]Pinar Heggernes. Minimal triangulations of graphs: a survey. Discrete Math., 306(3):297–317, 2006.
- [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]Michael O. Rabin. Decidability of second-order theories and automata on infinite trees. Trans. Amer. Math. Soc., 141:1–35, 1969.



















