# Minimal non-EPT graphs based on minimal non-interval graphs

Victoria Kaial, Annegret K Wagler

► To cite this version:

Victoria Kaial, Annegret K Wagler. Minimal non-EPT graphs based on minimal non-interval graphs.
2025. hal-05007099

HAL Id: hal-05007099

https://uca.hal.science/hal-05007099v1

Preprint submitted on 26 Mar 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# MINIMAL NON-EPT GRAPHS BASED ON
MINIMAL NON-INTERVAL GRAPHS

## (EXTENDED ABSTRACT)

Victoria Kaial*

Annegret K. Wagler*

## Abstract

Given a set $\mathcal{P}$ of paths over a graph, its edge intersection graph is a graph each of whose vertices corresponds to a path in $\mathcal{P}$ and where two vertices are connected if and only if the paths they correspond to share at least one edge. Interval and *EPT* are respectively the classes of edge intersection graphs over paths and trees. The complete characterisation of *EPT* graphs by minimal forbidden subgraphs is not yet known.

Since interval graphs are in particular *EPT* and, therefore, every non-*EPT* graph contains a minimal non-interval graph as an induced subgraph, where the complete list of the latter is known (Lekkerkerker, Boland, 1962), we first address the question of which minimal non-interval graphs are also minimal non-*EPT*. Some of the previously known minimal non-*EPT* graphs can be constructed by adding a vertex to a minimal non-interval graph (Golumbic, Jamison, 1985; Alcón, et.al., 2010). We complete the list of all minimal non-*EPT* graphs that can be obtained by adding exactly one vertex to a minimal non-interval graph.

## 1 Introduction

Graphs expressing the intersection of some objects play a role in many applications and are accordingly widely studied in the literature, see e.g. [2, 3, 4, 7]. In this paper, we consider intersection graphs of paths in a host graph $H$: given a collection $\mathcal{P}$ of paths over $H$, its *edge* (resp. *vertex*) intersection graph $EI(\mathcal{P})$ (resp. $VI(\mathcal{P})$) is a graph $G$ whose vertices are in a one-to-one correspondence with the paths in $\mathcal{P}$ where two vertices are adjacent if and only if the corresponding paths have at least one edge (resp. vertex) of $H$ in common; $(\mathcal{P}, H)$ is said to be an *EP* (resp. a *VP*) representation of $G$. Any graph admitting an *EP* (resp. a *VP*) representation in a host tree is said to be an *EPT* (resp.

<footnote>*University Clermont Auvergne, Clermont Auvergne INP, LIMOS (UMR 6158 CNRS), Clermont-Ferrand, France. E-mail: victoria.kaial@uca.fr, annegret.wagler@uca.fr</footnote>
<figure><img src="image_2.png" /><figcaption>Figure 1: Complete list of minimal non-VPT graphs [9]. In $F_{11}, \dots, F_{16}$, the vertices in the bold cycle form a clique. Figure from [9].</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Figure 2: Complete list of all minimal non-interval graphs by [8].</figcaption></figure>

a *VPT*) graph and the class formed by all *EPT* (resp. *VPT*) graphs is again called *EPT* (resp. *VPT*). The study of *EPT* and *VPT* graphs was initiated in 1985 by Golumbic & Jamison [5, 6] and by Monma & Wei [10] who also showed that the classes *EPT* and *VPT* are incomparable. While the class *VPT* is characterized by a complete list of minimal non-VPT graphs presented by Lévêque et. al [9] (see Figure 1), it has been shown in [6] that recognizing *EPT* graphs is NP-hard. Determining the complete list of minimal non-*EPT* graphs remains an open problem.

The aim of this paper is to study minimal non-EPT graphs, based on a characterization of interval graphs by minimal forbidden induced subgraphs due to Lekkerkerker and Boland [8], see Figure 2. In fact, interval graphs are the edge intersection graphs of subpaths over a path and thus form a subclass of EPT graphs. We observe the following:

**Observation 1.1.** Every non-EPT graph contains a minimal non-interval graph as induced subgraph.

In this paper, we study minimal non-EPT graphs from this perspective. A canonical
question in this context is the following:

**Problem 1.** Which minimal non-interval graphs are also minimal non-EPT?

We note that Golumbic and Jamison [6] showed that every $n$-hole $C_n$ for $n \ge 4$ is EPT (with a unique EPT-representation in a star) and exhaustively answered the question which EPT graphs can be obtained by adding one vertex to a hole as follows:

**Theorem 1.2 ([6]).** A graph obtained from an $n$-hole $C_n$ with $n \ge 4$ by adding one vertex $v$ is EPT if and only if $v$ has

* at most one neighbour in $C_n$,

* 2 or 3 consecutive neighbours on $C_n$,

* 2 pairs of 2 consecutive neighbours on $C_n$.

In consequence, every graph obtained from an $n$-hole $C_n$ by adding one vertex in a different way is non-EPT and minimal as all proper induced subgraphs are EPT or even interval graphs. Furthermore, three minimal non-EPT graphs are presented in [1] and analyzing their structure shows that they are obtained from the minimal non-interval graphs 2-net, 3-tent and 4-tent (see Figure 2) by adding a universal vertex (i.e. a vertex being adjacent to all other vertices). Accordingly, we pose the following problem:

**Problem 2.** Characterize the minimal non-EPT graphs obtained by adding one vertex to a minimal non-interval graph.

In Section 2, we present the resulting characterizations and close with some concluding remarks and lines of future research in Section 3.

## 2 New classes of minimal non-EPT graphs

To address Problem 1, we first recall that $n$-holes are shown to be EPT by [6], hence it is left to treat the remaining minimal non-interval graphs (see Figure 2). They are all chordal, i.e., without an $n$-hole $C_n$ for $n \ge 4$ as induced subgraph. Syslo showed in [11] that all chordal EPT graphs are VPT, and Monma & Wei [10] further proved that the class of chordal EPT graphs coincides with $VPT \cap EPT$. This implies:

**Observation 2.1.** Every chordal non-VPT graph is non-EPT.

Moreover, we can prove the following property of minimal non-EPT graphs:

**Lemma 2.2.** Every minimal non-EPT graph is 2-connected.

Combining these facts with the complete list of minimal non-VPT graphs from [9] in Figure 1 enables us to prove:

**Theorem 2.3.** The only minimal non-interval minimal non-EPT graphs are $n$-tents for $n \ge 5$.
<figure><img src="image_4.png" /><figcaption>Figure 3: All minimal non-EPT graphs $G \oplus v$ (where $v$ is not universal) for $G$ bipartite-claw, umbrella, $n$-tent $n \ge 3$) and $n$-net ($n \ge 2$) in that order from top left to bottom right. The vertex $v$ is indicated in black and its neighborhood in gray. Note the following pairs are isomorphic: $BC^4 \cong U^1$, $T_3^1 \cong N_2^2$, and $T_4^1 \cong N_3^4$.</figcaption></figure>

*Proof (sketch)* We treat all members of the complete list of minimal non-interval graphs from [8] (see Figure 2):

* Bipartite claw $BC$, umbrella $U$ and all $n$-nets $N_n$ for $n \ge 2$ are not 2-connected and thus not minimal non-EPT by Lemma 2.2.

* EPT representations of 3- and 4-tent can be constructed easily.

* All $n$-tents for $n \ge 5$ are minimal non-$VPT$ by [9] (see Figure 1, graphs $F_{10}(n)$, $n \ge 8$), thus also non-EPT by Observation 2.1, and minimal as all proper induced subgraphs are interval graphs.

* All $n$-holes $C_n$ for $n \ge 4$ are shown to be EPT by [6]. □

We next address the question which minimal non-EPT graphs can be obtained by adding one vertex $v$ to a minimal non-interval but EPT graph $G$, denoted by $G \oplus v$.

**Theorem 2.4.** The minimal non-EPT graphs $G \oplus v$ obtained by adding one vertex $v$ to a minimal non-interval graph $G$ are exactly the graphs where $G$ is

* an $n$-hole and the neighborhood of $v$ is different from the cases in Theorem 1.2;

* a bipartite claw, an umbrella, a 3-tent, a 4-tent or an $n$-net for $n \ge 2$ and either $v$ is universal or $G \oplus v$ is one of the graphs listed in Figure 3.

*Proof (sketch)* We have to treat all minimal non-interval EPT graphs $G$, i.e., all minimal non-interval graphs except $n$-tents with $n \ge 5$ by Theorem 2.3.
If $G$ is a hole $C_n$, we deduce the assertion from Theorem 1.2 by [6]. For all other minimal non-interval EPT graphs $G \neq C_n$,

* if $v$ is a universal vertex or $G \oplus v$ is $T_4^3$ or $U^2$, the graph $G \oplus v$ is chordal and minimal non-$VPT$ (see graphs $F_1, \dots, F_6$ and $F_9$ in Figure 1 by [9]), hence also non-$EPT$ by Observation 2.1;

* otherwise, $G \oplus v$ is minimal non-$EPT$ if and only if it is one of the non-chordal graphs listed in Figure 3.

In all cases, minimality follows from the fact that all proper induced subgraphs are $EPT$ or even interval graphs.

All other such graphs $G \oplus v$ are either $EPT$ (e.g. if they are not 2-connected) or contain a minimal non-$EPT$ graph as proper induced subgraph. This can be shown for $G$ being a bipartite claw, an umbrella, a 3-tent, a 4-tent or an $n$-net with $n \in \{2, 3, 4\}$ by a case analysis and for $n$-nets with $n \ge 5$ with the help of some technical lemmas. $\square$

## 3 Concluding remarks

In this work, we studied minimal non-$EPT$ graphs in relation to their minimal non-interval subgraphs and addressed the two problems of characterizing the minimal non-interval graphs that are also minimal non-$EPT$ and all minimal non-$EPT$ graphs obtained from a minimal non-interval but $EPT$ graph by adding one vertex. We showed that the $n$-tents for $n \ge 5$ are exactly the minimal non-interval minimal non-$EPT$ graphs and provided a complete list of all minimal non-$EPT$ graphs obtained from a minimal non-interval but $EPT$ graph, i.e., from bipartite claw, umbrella, 3-tent, 4-tent, $n$-nets for $n \ge 2$ and $n$-holes for $n \ge 4$, by adding one vertex. We note that adding a universal vertex to all of them except $C_4$ yields a minimal non-$EPT$ graph, and that for any $n$-net with $n \ge 5$, only adding a universal vertex results in a minimal non-$EPT$ graph.

Our lines of future research include finding and describing more minimal non-$EPT$ graphs, e.g., to characterize all minimal non-$EPT$ graphs containing a universal vertex, further minimal non-$EPT$ graphs obtained from minimal non-interval graphs by adding two or more vertices or by applying some operations to known minimal non-$EPT$ graphs.
References

[1] Liliana Alcón, Marisa Gutierrez, and María Pía Mazzoleni. A necessary condition for EPT graphs and a new family of minimal forbidden subgraphs. *Matemática Contem-porânea*, 39(13), 2010.

[2] Liliana Alcón, Maria Mazzoleni, and Tanilson Santos. Relationship among B1-EPG, VPT and EPT graphs classes. *Discussiones Mathematicae Graph Theory*, 43(3):841, 2023.

[3] Guillermo Durán, Luciano N Grippo, and Martín D Safe. Structural results on circular-arc graphs and circle graphs: a survey and the main open problems. *Discrete Applied Mathematics*, 164:427-443, 2014.

[4] Martin Charles Golumbic. *Algorithmic graph theory and perfect graphs*. Number 57 in Annals of discrete mathematics. Elsevier, Amsterdam, 2004.

[5] Martin Charles Golumbic and Robert E. Jamison. Edge and vertex intersection of paths in a tree. *Discrete Mathematics*, 55(2):151-159, 1985.

[6] Martin Charles Golumbic and Robert E Jamison. The edge intersection graphs of paths in a tree. *Journal of Combinatorial Theory, Series B*, 38(1):8-22, 1985.

[7] Victoria Kaial, Hervé Kerivin, and Annegret K. Wagler. On non-superperfection of edge intersection graphs of paths. *Discrete Optimization*, 54:100857, 2024.

[8] Cornelis Lekkerkerker and Johan Boland. Representation of a finite graph by a set of intervals on the real line. *Fundamenta Mathematicae*, 51(1):45-64, 1962.

[9] Benjamin Lévêque, Frédéric Maffray, and Myriam Preissmann. Characterizing path graphs by forbidden induced subgraphs. *Journal of Graph Theory*, 62(4):369-384, 2009.

[10] Clyde L Monma and Victor K Wei. Intersection graphs of paths in a tree. *Journal of Combinatorial Theory, Series B*, 41(2):141-181, 1986.

[11] Maciej M. Sysło. Triangulated edge intersection graphs of paths in a tree. *Discrete Mathematics*, 55(2):217-220, 1985.
# 4 Appendix: Omitted proofs

A graph $G = (V, E)$ is said to be *connected* if for every pair of vertices $u, v \in V$, there exists a path containing both $u$ and $v$; and *k-connected* if it remains connected after removing at most $k-1$ vertices. A *component* of a graph is a maximal connected subgraph.

When it is clear which EPT representation $(\mathcal{P}, T)$ of a graph $G$ we are referring to, $P(v)$ denotes the path in $\mathcal{P}$ corresponding to the vertex $v \in V(G)$. We also adopt the notation $G[V']$ to denote the subgraph of the graph $G$ induced by the subset $V'$ of its vertices.

*Proof of Lemma 2.2.* Suppose to the contrary that there is a minimal non-EPT graph $G$ having a vertex $v$ such that $G \setminus \{v\}$ is not connected. Then, $V(G) \setminus \{v\}$ can be partitioned into $V_1$ and $V_2$ such that there are no edges between $G[V_1]$ and $G[V_2]$.

Consider the subgraphs $G_1 = G[V_1 \cup \{v\}]$ and $G_2 = G[V_2 \cup \{v\}]$ of $G$. Since $G$ is minimal non-EPT, both $G_1$ and $G_2$ are EPT graphs, which implies the existence of an EPT representation $(\mathcal{P}_i, T_i)$ of $G_i$ for $i = 1, 2$.

For $i = 1, 2$, let $u_i$ in $T_i$ be one of the endpoints of the path $P_i(v) \in \mathcal{P}_i$. The tree $T$ obtained by identifying $T_1$ and $T_2$ in $u_1$ and $u_2$ hosts $\mathcal{P} = \mathcal{P}_1 \cup \mathcal{P}_2 \setminus \{P_1(v), P_2(v)\} \cup P(v)$, where $P(v) = P_1(v) + P_2(v)$; and $EI(\mathcal{P}) = G$. This gives an EPT representation $(\mathcal{P}, T)$ of $G$, which is a contradiction. □

In particular, a graph having a leaf (i.e. a vertex with degree 1 or, equivalently, with a single neighbour) is not 2-connected and hence non-EPT.

The following result from [6] regarding the unique EPT representation of holes is frequently used when proving a non-chordal graph to be non-EPT.

**Lemma 4.1** (Unique EPT representation of holes - Golumbic&Jamison, 1985 [6]). Let $G$ be an EPT graph with a hole $C = [c_1, c_2, \dots, c_n]$ and $(\mathcal{P}, T)$ an EPT representation of $G$. Then, $T$ contains a pie, i.e. an induced star $K_{1,n} = (\{v, v_1, v_2, \dots, v_n\}, \{\{v, v_i\} : i = 1, \dots, n\})$ with $\{v, v_i\}, \{v, v_{i+1}\} \in P(c_i)$ for each $i = 1, \dots, n$, as depicted below.

<figure><img src="image_5.png" /></figure>

*Proof of Theorem 2.3.* We treat all members of the complete list of minimal non-interval graphs from [8] (see Figure 2):

* Bipartite claw, umbrella and all $n$-nets for $n \ge 2$ have a vertex of degree 1. Hence, they are not 2-connected and thus not minimal non-EPT by Lemma 2.2. In fact, this implies they are EPT as all their proper induced subgraphs are interval graphs.
<figure><img src="image_6.png" /><figcaption>Figure 4: EPT representations of 3-tent and 4-tent (from left to right).</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Figure 5: Complete list of all minimal non-interval graphs by [8] with the vertex labelling used in the proofs. The bold vertices and edges of *n*-tent correspond to the subgraph considered in Lemma 4.10.</figcaption></figure>

• The graphs 3-tent and 4-tent are *EPT* (see Figure 4 for corresponding representations).

• All *n*-tents with *n* ≥ 5 are minimal non-VPT (see F₁₀(*n*) in Figure 1), thus also non-EPT by Observation 2.1, and minimal as all proper induced subgraphs are interval graphs.

• *n*-holes are *EPT* for all *n* ≥ 4 by [6] who showed that every *n*-hole has a *unique EPT*-representation, which has a star as host tree (see Lemma 4.1).

<figure><img src="image_8.png" /></figure>

To obtain Theorem 2.4, we first handle the case where the added vertex is universal, prove that the graphs in Figure 3 are minimal non-EPT, then present the corresponding proof for the infinite family of *n*-nets (*n* ≥ 5) preceded by the needed technical preliminary results, and finally give the analysis of the remaining individual candidates (i.e. the ones where *G* is a bipartite-claw, umbrella, 3- or 4-tent, or 2-, 3- or 4-net, and *v* is not a universal vertex).

Figure 5 shows the labelling of the vertices of the minimal non-interval graphs that will be used in the following proofs. We use the notation $G \circled v$ to refer to the graph $G \oplus v$ when $v$ is universal.

**Lemma 4.2.** *Adding a universal vertex to any EPT minimal non-interval graph but $C_4$ (i.e. bipartite claw, umbrella, *n*-net (for any *n* ≥ 2), 3-tent, 4-tent, $C_n$ (for any *n* ≥ 5)) results in a minimal non-EPT graph.*

*Proof.* Let $G$ be one of the other *EPT* minimal non-interval graphs and consider $G \circled v$. We observe that all such graphs are in the list of minimal non-VPT graphs ($F_1, \dots, F_5$ - see Figure 1) and, therefore, are non-EPT (see Observation 2.1).
<figure><img src="image_9.png" /><figcaption>Figure 6: Minimal non-`EPT` graphs $G_1$ and $G_2$ from [6], and $G_3$, $G_4$, $G_5$ from left to right.</figcaption></figure>

Minimality follows from the minimality of $G$ as a non-interval graph. Indeed, proper induced subgraphs of $G \circled{v}$ are either $G$, which is known to be *EPT*, or $G' \circled{v}$ for some proper induced subgraph $G'$ of $G$. In the latter case, $G'$ is an interval graph, which implies that $G' \circled{v}$ is an interval graph too (choosing $P(v)$ equal the host path). $\square$

Based on Lemma 4.1, Golumbic&Jamison [6] obtain Theorem 1.2, which can equiva-
lently be stated as follows.

**Corollary 4.3** (Golumbic, Jamison, 1985 [6]). *A graph obtained from an *n*-hole *C*<sub>*n*</sub> by adding one vertex *v* is non-*EPT* if and only if *v* has

• 2 or 3 non-consecutive neighbours on C_n,

• 4 neighbours on $C_n$ that are not 2 pairs of 2 consecutive vertices of $C_n$,

• 5 or more neighbours on $C_n$.

Minimality for the non-EPT graphs considered in Corollary 4.3 follows from the ob-
servation that a graph of the form $P \oplus v$ (where $P$ is a path) is always EPT.

In any non-chordal graph having a hole C, we call a vertex v outside of C to be C-
compatible if N_C(v) is one of the cases in Theorem 1.2, and C-incompatible otherwise (i.e.
if it is in one of the cases of Corollary 4.3). This implies further that more non-chordal
non-EPT graphs G = (V, E) can be obtained from a hole C by adding two or more C-
compatible vertices v in such a way that their adjacencies in G[V \ C] do not correspond
to the positions required for their paths P(v) in the unique representation of C. Figure 6
shows the graphs G_1 and G_2 from [6], and G_3, G_4, G_5 obtained that way.

**Lemma 4.4.** Every graph in Figure 3 is a minimal non-EPT graph.

*Proof.* We first observe:

* The graphs $U^2$ and $T_4^3$ are the minimal non-$VPT$ graphs $F_6$ and $F_9$ respectively (see Figure 1) and, therefore, non-$EPT$ by Observation 2.1.

* The graphs $BC_4$, $N_2^2$ and $N_3^4$ are isomorphic to other graphs in the list $(U^1, T_3^1$ and $T_4^1$ respectively) and will therefore not be treated separately in the proof.

For the remaining graphs, we identify proper subgraphs (highlighted in Figure 7), all
of whose *EPT* representations have a specific known structure - based on the above-stated
result (Lemma 4.1) regarding the unique *EPT* representation of holes. The conclusion
that they are non-*EPT* follows when trying to incorporate paths corresponding to the
remaining vertices. Indeed, the graphs
<figure><img src="image_10.png" /><figcaption>Figure 7: Illustration for the proof of Lemma 4.4</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Figure 8: An *EPT* graph (left) and its unique *EPT* representation (right).</figcaption></figure>

• $BC^1$, $U^1$ and $N_2^1$ have a hole C and some further vertices, each of which has one or two neighbours in C and is C-compatible, but connected with each other in an incompatible way.

• $T_3^1$, $T_4^1$, $N_3^1$ and $N_4^2$ contain a hole C and a vertex u with 3 or 4 consecutive neighbours in C that would force its path P(u) to use 2 specific edges of the pie hosting C in every EPT representation (if any), and further two to three C-compatible vertices connected with each other and with u in an incompatible way.

• $T_4^2$ and $N_3^3$ contain an induced $C_4 \oplus u$ and 3 further C-compatible vertices.

• $BC^2$, $BC^3$, $U^3$ and $N_3^2$ contain two holes of size 4 inducing the domino graph in Figure 8 (all of whose EPT representations must contain a substructure of the form shown in Figure 8) and two further vertices whose paths cannot be incorporated simultaneously to a representation of the first mentioned subgraph.

To prove minimality, we can easily find *EPT* representations of all corresponding proper induced subgraphs. □
The rest of the appendix is dedicated to proving that no minimal non-EPT graph other
than the ones listed in Theorem 2.4 is of the form $G \oplus v$ with $G$ minimal non-interval.

We first introduce some notation needed for the mentioned technical lemmas. Given a
set of paths $\mathcal{P}$ over a host graph $H$, the (not necessarily induced) subgraph of $H$ formed
by the edges and vertices used by at least one of the paths in $\mathcal{P}$ is referred to as *support
host graph of *$\mathcal{P}$* and we use the notation $H^*[\mathcal{P}]$.

**Lemma 4.5.** Let $G$ be a connected graph with EP-representation $(\mathcal{P}, H)$ on a host graph $H$. Then, the support host graph $H^*[\mathcal{P}]$ is connected too.

*Proof.* Let $\mathcal{P}$ be a set of paths over a graph $H$ and $G = I(\mathcal{P})$ its edge intersection graph.
Suppose that the support host graph $H^*[\mathcal{P}]$ is not connected.

Note that, for each $v \in V(G)$, all the vertices and edges of $P(v)$ belong to the same
component of $H^*[\mathcal{P}]$. Then, none of the paths in one component of $H^*[\mathcal{P}]$ can share an edge
with any of the paths in another component, which -under the condition that $H^*[\mathcal{P}]$ is not
connected and recalling that all vertices of $H^*[\mathcal{P}]$ belong to at least one path corresponding
to a vertex in $V(G)$ - implies that $G$ is not connected. $\square$

As a direct consequence of Lemma 4.5, we obtain Corollary 4.6, which is a key argument
in the subsequent proofs.

**Corollary 4.6.** Let $G = (V, E)$ be a graph admitting an EP-representation $(\mathcal{P}, H)$ and
let, for a vertex $v \in V$, $\bar{P}_v = \mathcal{P} \setminus \{\mathcal{P}(u) : u \in N[v]\}$.

If $G[V \setminus N[v]]$ is connected, then the support host graph $H^*[\overline{P_v}]$ must be contained in
one (connected) component of $H \setminus E(P(v))$, i.e., in one component of the graph obtained
from the host graph $H$ by removing the edges of the path $P(v) \in \mathcal{P}$.

**Lemma 4.7.** Let $P$ and $P^*$ be two paths over a tree $T$. Then, if $P$ and $P^*$ share one or more edges, the subgraph of $T$ induced by the set of common edges $E(P) \cap E(P^*)$ is connected. Moreover, this subgraph is a path.

*Proof.* Let $P$ and $P^*$ be two paths over a tree $T$ that share at least one edge. Supposing
the subgraph $T'$ induced by the set of common edges $E(P) \cap E(P^*)$ is not connected
would imply the existence of two vertices $v_1, v_2 \in V(T')$ that are not connected in $T'$.
However, as $T$ is a tree, there is a unique path $P$ between $v_1$ and $v_2$ in $T$. Then, since
$v_1, v_2 \in V(P) \cap V(P^*)$, the subpath of $P$ between $v_1$ and $v_2$ and the subpath of $P^*$ between
$v_1$ and $v_2$ is exactly $P$. This would imply that $E(P) \subseteq E(P) \cap E(P^*) = E(T')$, which
contradicts the assumption that $v_1$ and $v_2$ are not connected in $T'$. This leads to the
conclusion that $T'$ is connected.

Finally, the fact that $T'$ is a connected subgraph of a path implies that it is itself a
path. $\square$

**Lemma 4.8.** Let $P$ be a path over a tree $T$. Then, for each component $C$ of $T \setminus E(P)$, $|V(P) \cap V(C)| = 1$.
*Proof.* Let $T$ be a tree, $P$ a path over it, and $C$ a component of $T \setminus E(P)$.

We suppose first $|V(P) \cap V(C)| > 1$ and let $u, v \in V(P) \cap V(C)$ with $u \neq v$. As $C$ is connected, there is a path $P^*$ between $u$ and $v$ in $C$. By definition of $C$, $E(P^*) \subseteq E(T) \setminus E(P)$. In particular, $E(P^*)$ and the set of edges of the subpath of $P$ between $u$ and $v$ are disjoint. The latter implies the existence of two different paths between $u$ and $v$ in $T$, which contradicts the fact that $T$ is a tree. Since the contradiction comes from supposing $|V(P) \cap V(C)| > 1$, it can be concluded that $|V(P) \cap V(C)| \le 1$.

We suppose now that $|V(P) \cap V(C)| = 0$, consider vertices $u \in V(P)$ and $v \in C$, and let now $P^*$ be the path between $u$ and $v$ in $T$. We distinguish the following two cases: $E(P^*) \cap E(P) = \emptyset$ and $E(P^*) \cap E(P) \neq \emptyset$.

In the first case, $u$ is connected to $v$ in $T \setminus E(P)$ and therefore $u \in V(C)$, which is a contradiction because $u \in V(P)$ and we are assuming $V(P) \cap V(C) = \emptyset$.

In the second case, we know by Lemma 4.7 that $E(P^*) \cap E(P)$ is a subpath of $P$ which has $u$ and another vertex $w$ as endpoints. Then, the subpath of $P^*$ between $w$ and $v$ does not use any edges of $P$, which implies that $v$ and $w$ are in the same component of $T \setminus E(P)$. It follows that $w \in V(C)$, which is again a contradiction to the assumption that $V(P) \cap V(C) = \emptyset$. It can then be concluded that $V(P) \cap V(C) \neq \emptyset$.

This completes the proof. $\square$

Lemma 4.9 is a well-known characterization of the EPT representations of cliques and is used in particular in the proof of Lemma 4.10.

**Lemma 4.9 (Golumbic & Jamison, 1983 [6]).** If $(T, \mathcal{P})$ is an EPT representation of a graph $G$, then a subset $Q$ of $V(G)$ is a clique in $G$ if and only if it corresponds to a subcollection of paths of the form $\mathcal{P}[e] = \{P \in \mathcal{P} : e \in P\}$ for some edge $e$ in $T$ or $\mathcal{P}[K] = \{P \in \mathcal{P} : P \text{ contains } 2 \text{ edges of } K\}$ for some 3-star $K$ in $T$.

If $Q$ corresponds to $\mathcal{P}[e]$ for some edge $e \in E(T)$, $Q$ is said to be an edge clique; and if it corresponds to $\mathcal{P}[K]$ for some 3-star $K$ of $T$, it is a claw clique.

The following lemma is used in the proof of Lemma 4.11 to justify non-minimality of discarded candidates. Note that it also gives an alternative direct proof of the fact that $n$-tents are non-EPT for all $n \ge 5$.

**Lemma 4.10.** Let $G'$ be the subgraph of an $n$-tent ($n \ge 5$) induced by the vertices $a, b, c, d, e, 1, n-2$ (see Figure 2). A graph $G = (V, E)$ that has $G'$ as an induced subgraph and for which $G \setminus N[c]$ is connected, is non-EPT.

*Proof.* Let $G$ be a graph having the subgraph of $n$-tent ($n \ge 5$) induced by the vertices $a, b, c, d, e, 1, n-2$ (see Figure 5) as an induced subgraph. We suppose for the sake of contradiction that $G$ is EPT and let $(H, \mathcal{P})$ be an EPT representation of $G$.

Since $G \setminus N[e], G \setminus N[a]$ and $G \setminus N[c]$ are connected, Lemma 4.6 implies that for each $i \in \{a, c, e\}$, $H^*[\overline{\mathcal{P}_i}]$ is contained in one component $C_i$ of $H \setminus E(P(i))$. In particular, we have $E(\mathcal{P}(\{n-2, c, d, e\})) \subseteq C_a$, $E(\mathcal{P}(\{1, n-2, a, e\})) \subseteq C_c$, and $E(\mathcal{P}(\{1, a, b, c\})) \subseteq C_e$.

Lemma 4.8 guarantees (for each $i \in \{a, c, e\}$) the existence of a unique vertex $v_i \in V(P(i)) \cap C_i$. Moreover, as $N_G(d)$ has nonempty intersection with both $\{e\}$ and $V(G) \setminus N_G[e]$, we conclude that $v_e \in P(d)$. Analogous reasoning leads to
* $v_e \in P(d) \cap P(n-2)$,

* $v_a \in P(1) \cap P(b)$, and

* $v_c \in P(d) \cap P(b)$.

Note that this implies that $P(d)$ contains the unique path between $v_e$ and $v_c$, and $P(b)$ contains the unique path between $v_a$ and $v_c$.

The presence of the edges $\{a, b\}$, $\{d, e\}$ and the absence of the edges $\{a, e\}$, $\{a, c\}$, $\{e, c\}$ in the graph $G$ have the following consequences in the EPT representation:

* $E(P(a)) \cap E(P(b)) \neq \emptyset$ and $E(P(d)) \cap E(P(e)) \neq \emptyset$,

* $E(P(a)) \cap E(P(e)) = \emptyset$, and

* $E(P(a)) \cup E(P(e)) \subseteq E(P(V(T_n) \setminus N[c])) \subseteq C_c$;

which together imply that the paths $P(d)$ and $P(b)$ "split" at some point in $C_c$. Formally, the latter means that there exist vertices $w, w_b, w_d \in C_c$ and $w_0$ such that $\{w_0, w\} \in P(d) \cap P(b)$, $\{w, w_d\} \in P(d) \setminus P(b)$ and $\{w, w_b\} \in P(b) \setminus P(d)$.

We arrive at a contradiction distinguishing two cases. Namely, the case where $w$ is one of the already mentioned vertices $v_a$ or $v_e$ and the case where $w$ is a different vertex.

We first assume $v_a, v_e \neq w$ and observe that, in order to satisfy $\{n-2, b\}$, $\{d, 1\} \in E(G)$, the paths $P(1)$ and $P(n-2)$ must use two edges of the claw $\{w, w_0, w_d, w_b\}$ each. As $P(d)$ and $P(b)$ use two edges of this claw each as well, by Lemma 4.9, $\{d, n-2, 1, b\}$ is a clique in $T_n$, which contradicts the fact that $\{n-2, 1\} \notin E(G)$.

For the second case, we assume w.l.o.g. that $w = v_e$. Since $\{d, e\} \in E(T_n)$, $w = v_e \in P(d) \cap P(e)$ and, $P(d) \cap P(e)$ is a path (by Lemma 4.7), we conclude that $\{w, w_d\} \in P(e)$. Then, recalling that $v_a \in P(1)$ and $\{1, d\} \in E(T_n)$ but $\{1, e\} \notin E(T_n)$, we have that the unique path between $v_a$ and $w_0$ is contained in $P(1)$.

If $v_a \neq w$, the path $P(n-2)$ should use either $\{w, w_0\}$ or $\{w, w_b\}$ in order to share an edge with $P(b)$. But since $P(1)$ uses both of these edges (as they lay in this case on the path between $v_a$ and $w_0$), this would contradict the fact that $\{1, n-2\} \notin E(G)$.

If $v_a = w$, the intersection of $P(a)$ and $P(b)$ is a path (Lemma 4.7) containing $w$ and at least one edge (since $\{a, b\} \in E(T_n)$). Then, recalling that $\{w_0, w\}$, $\{w, w_b\} \in P(b)$, $\{w, w_0\} \in P(d)$, and $\{a, d\} \notin E(G)$, we can conclude that the path $P(a)$ uses the edge $\{w, w_b\}$. Finally, since $w \in P(b) \cap P(n-2)$ and $\{w, w_b\}$, $\{w, w_0\} \in P(b)$, the path $P(2-n)$ should contain at least one of these two edges in order to share at least one edge with $P(b)$. But both of them are used by paths $(P(1)$ and $P(a))$ that do not share any edges with $P(n-2)$.

As anticipated, we arrive at a contradiction and conclude that $G$ is not EPT. □

**Lemma 4.11** (n-net, $n \ge 5$). A graph of the form $N_n \oplus v$ with $n \ge 5$ is minimal non-EPT if and only if $v$ is universal.
*Proof.* Let $n \ge 5$ and $G = N_n \oplus v$, and suppose $G$ is minimal non-EPT. We prove that $v$ needs to be universal. Note first that $b_0, b_{n+1}, w \in N(v)$ is required to ensure 2-connectivity, which is necessary by Lemma 2.2.

**Claim 1.** For each $i \in \{3, 4, \dots, n-2\}$, $b_i \in N(v)$, and $a \in N(v)$.

Let $i \in \{3, 4, \dots, n-2\}$ and consider an EPT representation $(\mathcal{P}, T)$ of $G \setminus w$. Since $b_1, b_i, b_n$ is a stable set, $P(b_1) \cap P(a)$, $P(b_i) \cap P(a)$ and $P(b_n) \cap P(a)$ are pairwise edge-disjoint. On the other hand, since $b_1$ and $b_n$ are in the same component of $G \setminus N[b_n]$, the paths $P(b_1)$ and $P(b_i)$ are completely contained in the same component of $T \setminus E(P(b_n))$; and, similarly, $b_i$ and $b_n$ lay in the same component of $T \setminus E(P(b_1))$. Then, $P(b_i) \cap P(a)$ is "strictly inbetween" $P(b_1) \cap P(a)$ and $P(b_n) \cap P(a)$, which implies that $P(b_1)$ and $P(b_n)$ lay in different components of $T \setminus (E(P(b_i) \cap P(a)))$. The latter leads to the conclusion that $v \in N(b_i)$ because, otherwise $G' \setminus N[b_i]$ would be connected, in which case $P(b_1)$ and $P(b_n)$ should be contained in the same component of $T \setminus E(P(b_i))$ (Lemma 4.5).

**Claim 2.** At least one of the vertices $b_1, b_n$ is in $N(v)$.

Suppose $b_1, b_n \notin N(v)$. If $n=5$ and $b_4 \notin N(v)$, the vertices $v, b_3, b_4, b_5, b_6$ induce a hole $C_5$ which, together with the vertices $b_2, a, w$, induce the non-EPT graph $G_5$. Otherwise, the vertices in $N(a)$ (possibly excluding $b_1$ and/or $b_n$) induce a smaller net, which implies by Lemma 4.2 that $G \setminus \{b_0, b_{n+1}\}$ is non-EPT and, therefore, $G$ is non-EPT but also not minimal.

**Claim 3.** $b_1, b_2, b_{n-1}, b_n \in N(v)$.

We show that, otherwise, $G$ contains a proper induced subgraph satisfying the conditions of Lemma 4.10. If $b_n \in N(v)$, $b_1 \notin N(v)$, we take $G \setminus b_0$. If $b_n \in N(v)$, $b_2 \notin N(v)$, we take $G \setminus \{b_0, b_1\}$. Note that any other candidate belongs to one of those two cases. $\square$

Note that it can be concluded from the proof of Lemma 4.11 that every 2-connected graph of the form $N_n \oplus v$ with $n \ge 5$ is non-EPT.

**Lemma 4.12 (Bipartite-claw).** The minimal non-EPT graphs of the form $BC \oplus v$ are exactly $BC^1, \dots, BC^4$ (see Figure 3), and $BC \ominus v$.

*Proof.* Graphs of the form $BC \oplus v$ where $v$ is not adjacent to all three leaves $a_1, a_2, a_3$ are not minimal non-EPT graph due to Lemma 2.2. All other graphs $BC \oplus v$ are non-EPT, either containing a hole $C$ and a $C$-incompatible vertex as a proper induced subgraph, or being one of the graphs $BC_1, \dots, BC_4, BC \ominus v$. The latter have already been proven to be minimal non-EPT in Lemma 4.2 and Lemma 4.4. $\square$

In the following proofs, we omit repetition of symmetric cases without further notice.

**Lemma 4.13 (Umbrella).** The minimal non-EPT graphs of the form $U \oplus v$ are exactly $U^1, U^2, U^3$ (see Figure 3), and $U \ominus v$.

*Proof.* First note the 2-connectivity property (Lemma 2.2) implies that in every minimal non-EPT graph of that form $U \oplus v$, the vertex $v$ has at least two neighbours - one of them being the leaf $c$.

The candidates where $c \in N(v)$ and additionally satisfy:
* $b_1, b_4 \in N(v)$ and $b_2, b_3 \notin N(v)$ (or, symmetrically, $b_2, b_5 \in N(v)$ and $b_3, b_4 \notin N(v)$) contain a hole $C$ induced by $v, b_1, b_2, b_3, c$ and a $C$-incompatible vertex $b_4$.

* $b_1, b_5 \in N(v)$ and $b_2, b_3, b_4 \notin N(v)$ contain a hole $C$ induced by $v, b_1, \dots, b_5$ and a $C$-incompatible vertex $c$.

* $b_2, b_4, c \in N(v)$ and $b_3 \notin N(v)$ contain a hole $C$ induced by $v, b_2, b_3, b_4$ and a $C$-incompatible vertex $c$.

The ones where the neighborhood of $v$ is exactly (or symmetric to):

* $\{b_1, b_2, b_3, b_4, c\}, \{b_1, b_2, b_3, b_4, b_5, c\}$ contain $G_1$ as a proper induced subgraph.

* $\{b_1, b_2, b_4, c\}, \{b_1, b_3, b_4, c\}, \{b_1, b_2, b_3, b_5, c\}$ contain $G_2$ as a proper induced subgraph.

The graph $U \oplus v$ with $N(v) = \{b_1, b_3, b_5, v\}$ has a hole $C$ induced by $b_1, a, b_5, v$ and a $C$-incompatible vertex $b_3$.

The four graphs $U^1, U^2, U^3, U \oplus v$ have already been proven to be minimal non-EPT in Lemma 4.2 and Lemma 4.4

The remaining candidates are EPT.

**Lemma 4.14 (n-tent).** The minimal non-EPT graphs of the form $T_n \oplus v$ ($n \ge 3$) are exactly $T_3^1, T_4^1, T_4^2, U^3$ (see Figure 3), $T_3 \oplus v$, and $T_4 \oplus v$.

*Proof.* If $n \ge 5$, n-tent is non-EPT (see Theorem 2.3) and therefore every graph of the form $T_n \oplus v$ ($n \ge 5$) is non-EPT, but none of them is minimal. The graphs $T_3^1, T_4^1, T_4^2, U^3$ (see Figure 3), $T_3 \oplus v$, and $T_4 \oplus v$ have already been proven to be minimal non-EPT in Lemma 4.4 and Lemma 4.2. Due to Lemma 2.2, in every minimal non-EPT graph of the form $T_n \oplus v$, the vertex $v$ has at least two neighbours. We analyse the remaining candidates.

The graph of the form $T_3 \oplus v$ where $N(v)$ is exactly (or symmetric to)

* $\{a, c, e\}$ or $\{a, e, 1\}$ has a hole $C$ induced by the vertices $a, b, d, e, v$ and a $C$-incompatible vertex ($c$ and $1$ respectively).

* $\{a, b, d, e\}$ or $\{a, b, c, d, e\}$ contains the graph $G_1$ as a proper induced subgraph ($T_3 \oplus v \setminus c$).

* $\{a, b, e\}$ contains $G_2$ as a proper induced subgraph ($T_3 \oplus v \setminus c$).

The following table shows the non-minimality arguments for the remaining non-EPT candidates of the form $T_4 \oplus v$.

<table><thead><tr><th>a</th><th>b</th><th>c</th><th>d</th><th>e</th><th>1</th><th>2</th><th>EPT</th><th>minimal</th><th>proper induced subgraph</th><th>induced by</th></tr></thead><tbody><tr><td>x</td><td></td><td>x</td><td></td><td></td><td></td><td></td><td>no</td><td>no</td><td>G<sub>4</sub></td><td>V \ e</td></tr><tr><td>x</td><td></td><td></td><td>x</td><td></td><td></td><td></td><td>no</td><td>yes</td><td>-</td><td>-</td></tr><tr><td></td><td>x</td><td></td><td></td><td></td><td></td><td>x</td><td>no</td><td>no</td><td>N<sub>2</sub> &oplus; v</td><td>V \ e</td></tr></tbody></table>
<table><tr><td>x</td><td>x</td><td>x</td><td></td><td></td><td></td><td>no</td><td>no</td><td>C<sub>5</sub> ⊗ v</td><td>V \ {e, 2}</td></tr><tr><td>x</td><td>x</td><td></td><td>x</td><td></td><td></td><td>no</td><td>yes</td><td>-</td><td>-</td></tr><tr><td>x</td><td></td><td>x</td><td>x</td><td></td><td></td><td>no</td><td>no</td><td>G<sub>2</sub></td><td>V \ {e, 2}</td></tr><tr><td>x</td><td></td><td>x</td><td></td><td>x</td><td></td><td>no</td><td>no</td><td>hole + incompatible vertex</td><td>V \ {b, 2}</td></tr><tr><td>x</td><td></td><td>x</td><td></td><td></td><td>x</td><td>no</td><td>no</td><td>G<sub>2</sub></td><td>V \ {e, 2}</td></tr><tr><td>x</td><td></td><td>x</td><td></td><td></td><td>x</td><td>no</td><td>no</td><td>hole + incompatible vertex</td><td>V \ {b, e}</td></tr><tr><td>x</td><td></td><td></td><td>x</td><td>x</td><td></td><td>no</td><td>no</td><td>N<sub>2</sub> ⊗ v</td><td>V \ a</td></tr><tr><td>x</td><td></td><td></td><td>x</td><td></td><td>x</td><td>no</td><td>no</td><td>G<sub>2</sub></td><td>V \ {c, e}</td></tr><tr><td>x</td><td>x</td><td>x</td><td>x</td><td></td><td></td><td>no</td><td>no</td><td>G<sub>3</sub></td><td>V \ e</td></tr><tr><td>x</td><td>x</td><td>x</td><td></td><td>x</td><td></td><td>no</td><td>no</td><td>hole + incompatible vertex</td><td>V \ {b, 2}</td></tr><tr><td>x</td><td>x</td><td>x</td><td></td><td></td><td>x</td><td>no</td><td>no</td><td>G<sub>3</sub></td><td>V \ e</td></tr><tr><td>x</td><td>x</td><td>x</td><td></td><td></td><td>x</td><td>no</td><td>no</td><td>C<sub>5</sub> ⊗ v</td><td>V \ {e, 2}</td></tr><tr><td>x</td><td>x</td><td></td><td>x</td><td>x</td><td></td><td>no</td><td>yes</td><td>-</td><td>-</td></tr><tr><td>x</td><td></td><td>x</td><td>x</td><td></td><td>x</td><td>no</td><td>no</td><td>G<sub>1</sub></td><td>V \ {e, 2}</td></tr><tr><td>x</td><td></td><td>x</td><td></td><td>x</td><td>x</td><td>no</td><td>no</td><td>hole + incompatible vertex</td><td>{v, a, b, c, 2}</td></tr><tr><td>x</td><td></td><td>x</td><td></td><td>x</td><td>x</td><td>no</td><td>no</td><td>hole + incompatible vertex</td><td>{v, c, d, e, 1}</td></tr><tr><td>x</td><td></td><td>x</td><td></td><td></td><td>x</td><td>no</td><td>no</td><td>G<sub>2</sub></td><td>V \ {e, 1}</td></tr><tr><td>x</td><td></td><td>x</td><td></td><td>x</td><td></td><td>no</td><td>no</td><td>G<sub>3</sub></td><td>V \ e</td></tr><tr><td>x</td><td></td><td>x</td><td></td><td>x</td><td>x</td><td>no</td><td>no</td><td>T<sub>3</sub> ⊗ v</td><td>V \ e</td></tr><tr><td>x</td><td></td><td>x</td><td></td><td>x</td><td>x</td><td>no</td><td>no</td><td>hole + incompatible vertex</td><td>{v, c, d, e, 1}</td></tr><tr><td>x</td><td></td><td>x</td><td></td><td>x</td><td>x</td><td>no</td><td>no</td><td>G<sub>1</sub></td><td>V \ {e, 2}</td></tr><tr><td>x</td><td></td><td>x</td><td></td><td>x</td><td>x</td><td>no</td><td>no</td><td>hole + incompatible vertex</td><td>{v, a, b, c, 2}</td></tr><tr><td>x</td><td></td><td>x</td><td></td><td>x</td><td>x</td><td>no</td><td>no</td><td>G<sub>2</sub></td><td>V \ {a, 1}</td></tr><tr><td>x</td><td></td><td>x</td><td></td><td>x</td><td>x</td><td>no</td><td>no</td><td>T<sub>3</sub> ⊗ v</td><td>V \ e</td></tr><tr><td>x</td><td></td><td>x</td><td></td><td>x</td><td>x</td><td>no</td><td>no</td><td>G<sub>1</sub></td><td>V \ {a, 1}</td></tr></table>

□

**Lemma 4.15** ($N_2 \oplus v$, $N_3 \oplus v$, $N_4 \oplus v$). The minimal non-EPT graphs of the form $N_n \oplus v$ ($n = 2, 3, 4$) are exactly $N_2^1, N_2^2, N_3^1, \dots, N_3^4, N_4^1$ (see Figure 3), and $N_n \oplus v$ ($n = 1, 2, 3$).

*Proof.* It was already proven in Lemma 4.2 and Lemma 4.4 that $N_2^1, N_2^2, N_3^1, \dots, N_3^4, N_4^1$ and $N_n \oplus v$ ($n = 1, 2, 3$) are minimal non-EPT.

Due to Lemma 2.2, in every minimal non-EPT graph of the form $N_n \oplus v$, the vertex $v$ is connected to all three leaves $b_0, b_{n+1}, w$.

For $n = 2, 3$, every remaining candidate different from $N_2^1, N_2^2, N_3^1, \dots, N_3^4, N_2 \oplus v$, $N_3 \oplus v$ contains a proper induced subgraph composed of a hole $C$ and a $C$-incompatible vertex and is, therefore, non-minimal non-EPT.

For $n = 4$, every remaining candidate where $a$ is not in the neighbourhood of $v$ contains a hole $C$ and a $C$-incompatible vertex that makes it non-minimal non-EPT. All others satisfy $V' = \{a, b_0, b_5, w\} \subseteq N(v)$ and are non-minimal non-EPT. Indeed, the graph $N_4 \oplus v$ with:
* $N(v) = V'$, $N(v) = V' \cup \{b_1\}$, or $N(v) = \{b_1, b_4\}$ contains a hole C of size at most 7 and a C-incompatible vertex.

* $N(v) = V' \cup \{b_3\}$ contains $G_5$ as a proper induced subgraph.

* $N(v) = V' \cup \{b_1, b_3\}$ or $N(v) = V' \cup \{b_1, b_2, b_3\}$ contains a graph satisfying the conditions of Lemma 4.10 as a proper induced subgraph.

* $N(v) = V' \cup \{b_2, b_3\}$ contains $N_2 \oplus v$ as a proper induced subgraph.

* $N(v) = V' \cup \{b_1, b_2, b_4\}$ contains $T_4 \oplus v$ as a proper induced subgraph.

In the last four items above, the mentioned subgraph corresponds to the one induced by all vertices but $b_5$. $\square$