Characterization of word-representable split graphs with an independent set of fixed size

1. Introduction

The theory of word-representable graphs, first introduced by Sergey Kitaev and Steven Seif in the setting of Perkins semigroups [11], has become a rich area of research with strong connections to algebra, graph theory, and combinatorics on words. This graph class, which generalizes important classes such as circle graphs, comparability graphs, and 3-colorable graphs, has been extensively studied in monographs [6, 8]. Computational tools like Glen’s software have further supported their analysis and construction. Notably, recognizing whether a graph is word-representable or not is an NP-complete problem.

An orientation of a graph is transitive if the presence of \(u \rightarrow v\) and \(v \rightarrow z\) implies \(u \rightarrow z\). Graphs that admit such an orientations are called comparability graphs.

An orientation of a graph is said to be semi-transitive if it is acyclic and satisfies the following condition: for any directed path \(u_1 \rightarrow u_2 \rightarrow \cdots \rightarrow u_t\) with \(t \geq 2\), either there is no edge from \(u_1\) to \(u_t\), or the subgraph induced by the vertices \(u_1, \ldots, u_t\) forms a transitive tournament, i.e, all possible edges \(u_i \rightarrow u_j\) exist for every \(i < j\). An undirected graph is said to be semi-transitive if it can be oriented in such a way that the resulting digraph is semi-transitive. This notion of semi-transitive orientation was introduced in [4] as a tool for characterizing word-representable graphs (Theorem 2.1).

A class \(\mathcal{X}\) of graphs is said to be hereditary if it is closed under taking induced subgraphs; that is, if \(G \in \mathcal{X}\), then every induced subgraph of \(G\) also belongs to \(\mathcal{X}\). For any hereditary class \(\mathcal{X}\), we have \(\mathcal{X} = \text{Free}(\text{Forb}(\mathcal{X}))\), where \(\text{Forb}(\mathcal{X})\) denotes the set of all minimal forbidden induced subgraphs for \(\mathcal{X}\), and \(\text{Free}(\mathcal{M})\) denotes the class of graphs that do not contain any graph from \(\mathcal{M}\) as an induced subgraph [8]. The class of word-representable graphs is a hereditary graph class [6].

A graph \(G = (V(G), E(G))\) is said to be a split graph if its vertex set \(V(G)\) can be partitioned into two disjoint subsets, where one subset induces a clique and the other subset induces an independent set [3]. Throughout this work, we assume that the clique is of maximum possible size, i.e., no vertex in the independent set is adjacent to all vertices in the clique.

Split graphs have received considerable attention in the literature due to their rich structural properties and diverse applications (see, e.g., [3] and references therein). A forbidden induced subgraph characterization for the class of split comparability graphs can be found in [3]. In the context of word-representability, it is known that while some split graphs admit semi-transitive orientations, others do not. Since word-representable split graphs form a subclass of the hereditary class of word-representable graphs, this subclass has been the subject of several recent works [2, 5, 7, 10], together with efforts to obtain characterizations via minimal forbidden induced subgraphs. Although partial progress has been made, a complete classification remains open.

In this work, we study a specific subclass of split graphs, namely those with an independent set of size four, addressing an open problem posed by Kitaev and Pyatkin [9, 10].

In parallel with the development of this work, a subsequent manuscript available on arXiv (see [13]) presents a complete characterization of word-representable split graphs. That work explicitly builds, in part, on preliminary results from an earlier version of the present paper (see [12]). In particular, the graph \(D_1\) and the idea of reducing the problem to a finite collection of exhaustive cases first appeared in [12].

While the later manuscript ([13]) gives a global characterization of split graphs, the present paper is devoted to the case of split graphs with an independent set of size four and develops this setting in substantially greater structural detail. The proofs, intermediate lemmas, remarks and observations, together with the structural Theorems 3.5–3.13 and the systematic case analysis presented here, are original contributions of the present work.

Accordingly, the contribution of this manuscript lies not only in the characterization of the \(|E|=4\) case, but also in the explicit proof framework developed for it. In particular, we introduce constructive labeling methods, reusable forbidden-induced-subgraph criteria, and a decomposition of the search space into finitely many non-isomorphic configurations. These methods provide transparent proofs for the \(|E|=4\) case, suggest possible approaches and case decompositions for broader generalizations, and motivate further conjectural directions. They may also be useful more broadly in the study of graph classes defined through vertex labelings in the context of word-representability.

The remainder of the paper is organized as follows. Section 2 reviews existing results on the word-representability of split graphs. Section 3 presents our characterization of word-representable split graphs with an independent set of size four in terms of minimal forbidden induced subgraphs. Finally, Section 4 concludes with a conjecture and discusses possible approaches toward a complete characterization.

2. Preliminaries

One of the key developments in the study of word-representable graphs is their characterization in terms of semi-transitive orientations, which forms the basis for many subsequent results. We begin this section by stating the fundamental theorem below. For a comprehensive account of the theory and related results, see [3, 2, 5, 7, 10].

Theorem 2.1. [4] A graph is word-representable if and only if it admits a semi-transitive orientation.

The notion of semi-transitive orientation extends the classical concept of transitive orientation.

Theorem 2.2. [4] Let \(n\) be the number of vertices in a graph \(G\), and let \(x \in V(G)\) be a vertex of degree \(n – 1\) (called an universal vertex). Let \(H = G \setminus \{x\}\) be the graph obtained by removing \(x\) and all edges incident to it. Then, \(G\) is word-representable if and only if \(H\) is a comparability graph.

Let \(S_n = (E_{n-m}, K_m)\) be a split graph on \(n\) vertices, where the vertex set is partitioned into a maximal clique \(K_m\) on \(m\) vertices and an independent set \(E_{n-m}\) on \(n – m\) vertices. Each vertex in \(E_{n-m}\) has degree at most \(m – 1\).Throughout this work, we use \(E\) to denote an independent set, \(K\) to denote a clique, \(N(v)\) to denote the neighborhood of a vertex \(v\), and \(G\setminus \{v\}\) to denote the graph obtained from \(G\) by deleting the vertex \(v\) together with all edges incident to \(v\).

Theorem 2.3. [3] Let \(S_n = (E_{n-m}, K_m)\) be a split graph. Then it is a comparability graph if and only if it contains none of \(B_1, B_2, B_3\) (as shown in Figure 1) as induced subgraphs.

The following theorem highlights a notable property of transitive orientations when applied to cliques.

Theorem 2.4. [7] Let \(K_m\) be a clique on \(m\) vertices in a graph \(G\). Then, any acyclic orientation of \(G\) induces a transitive orientation on \(K_m\). In particular, every semi-transitive orientation of \(G\) yields a transitive orientation on \(K_m\). Moreover, in both cases, the induced orientation on \(K_m\) contains exactly one source and one sink (as shown in Figure 2).

The following two theorems describe the structure of semi-transitive orientations in word-representable split graphs.

Theorem 2.5. [7] Let \(S_n = (E_{n-m}, K_m)\) be a split graph, and let \(P = p_1 \rightarrow p_2 \rightarrow \cdots \rightarrow p_m\) be the longest directed path in \(K_m\). Then, any semi-transitive orientation of \(S_n\) partitions the vertices in the independent set \(E_{n-m}\) into three (possibly empty) categories:

• A vertex is of type A if it is a source and is adjacent to all vertices in the set \(\{p_i, p_{i+1}, \ldots, p_j\}\) for some \(1 \leq i \leq j \leq m\).

• A vertex is of type B if it is a sink and is adjacent to all vertices in the set \(\{p_i, p_{i+1}, \ldots, p_j\}\) for some \(1 \leq i \leq j \leq m\).

• A vertex is of type C if it has an incoming edge from every vertex in the set \(I_v = \{p_1, p_2, \ldots, p_i\}\) and an outgoing edge to every vertex in the set \(O_v = \{p_j, p_{j+1}, \ldots, p_m\}\), for some \(1 \leq i < j \leq m\). Here \(I_v\) and \(O_v\) are called the source group and the sink group of vertex \(v\), respectively.

Theorem 2.6. [7] Let \(S_n = (E_{n-m}, K_m)\) be a graph with a semi-transitive orientation, where \(P = p_1 \rightarrow p_2 \rightarrow \cdots \rightarrow p_m\) is the longest directed path in \(K_m\). For a vertex \(x \in E_{n-m}\) of Type C, the following conditions must be satisfied:

• There does not exist any vertex \(y \in E_{n-m}\) of Type A or Type B that is adjacent to both \(p_{|I_x|}\) and \(p_{m – |O_x| + 1}\).

• Furthermore, there is no vertex \(y \in E_{n-m}\) of Type C such that either its source group \(I_y\) or sink group \(O_y\) contains both \(p_{|I_x|}\) and \(p_{m – |O_x| + 1}\).

By combining the previous results, the semi-transitive orientations of split graphs can be fully classified as follows:

Theorem 2.7. [7] An orientation of a split graph \(S_n = (E_{n-m}, K_m)\) is semi-transitive if and only if the following conditions hold:

• \(K_m\) is oriented transitively.

• Each vertex in \(E_{n-m}\) is of one of the three types described in Theorem 2.5.

• The restrictions in Theorem 2.6 are satisfied.

Next, we state an equivalent formulation of the above theorem in terms of the neighborhood \(N(v)\) of a vertex \(v \in E\).

Theorem 2.8. [10] A split graph \(S=(E_{n-m}, K_m)\) is semi-transitive if and only if the vertices of the clique \(K_m\) can be labeled from 1 to \(m\) such that the following conditions hold:

• For each \(v \in E_{n-m}\), the neighborhood \(N(v) \subseteq K_m\) is of the form \([a, b]\) with \(a \leq b\), or \([1, a] \cup [b, m]\) with \(a < b\).

• If \(N(u) = [a_1, b_1]\) and \(N(v) = [1, a_2] \cup [b_2, m]\), with \(a_1 \leq b_1\) and \(a_2 < b_2\), then either \(a_1 > a_2\) or \(b_1 < b_2\).

• If \(N(u) = [1, a_1] \cup [b_1, m]\) and \(N(v) = [1, a_2] \cup [b_2, m]\), with \(a_1 < b_1\) and \(a_2 < b_2\), then \(a_2 < b_1\) and \(a_1 < b_2\).

Here, for any integers \(a \leq b\), the notation \([a, b]\) denotes the set \(\{a, a+1, \ldots, b\}\).

In the following, we present an equivalent formulation of Theorem 2.8, which will be used throughout the paper to verify more easily whether a given labeling of the clique vertices satisfies the conditions of Theorem 2.8.

Theorem 2.9 (Equivalent form of Theorem 2.8). A split graph \(S = (E_{n-m}, K_m)\) is word-representable if and only if the vertices of \(K_m\) can be labeled from \(1\) to \(m\) and arranged in a circular order such that the following conditions hold for every \(v \in E_{n-m}\):

• The neighborhood \(N(v)\) forms a consecutive block in the circular order (see Figure 3 (left)). This condition is equivalent to the first condition of Theorem 2.8.

• There is no vertex \(u\in E_{n-m}\) such that \(N(u)\) contains the complementary block of \(N(v)\); that is, the consecutive block of vertices encountered when moving around the circle from the last vertex of \(N(v)\) back to its first vertex (see Figure 3 (right)). More precisely, without loss of generality, if \(N(v)=\{1,2,\ldots,i\},\;\text{for}\;i<m,\) then the complementary block of \(N(v)\) is \(\{i,i+1,i+2,\ldots,m,1\}.\) This condition is equivalent to the remaining two conditions of Theorem 2.8.

Proof. (Justification of equivalence). The equivalence follows directly from the interpretation of the linear labeling \(1,2,\ldots,m\) as a circular order of the clique vertices.

Under the labeling of Theorem 2.8, a neighborhood of the form \([a,b]\) is an ordinary interval in the linear order, while a neighborhood of the form \([1,a]\cup[b,m]\) is an interval that wraps around the ends of the labeling. When the vertices \(1,2,\ldots,m\) are placed on a circle in this order, both types become precisely consecutive blocks of vertices on the circle. Hence, the first condition of Theorem 2.8 is equivalent to the first condition of Theorem 2.9.

For the remaining conditions, observe that if \(N(v)=[1,a_2]\cup[b_2,m]\), then its complementary block is \([a_2,b_2]=\{a_2,a_2+1,\ldots,b_2\}.\) Thus, for a neighborhood \(N(u)=[a_1,b_1]\), the containment of the complementary block of \(N(v)\) in \(N(u)\) occurs precisely when \(a_1\le a_2\;\;\text{and}\;\; b_1\ge b_2.\) Therefore, forbidding such containment is equivalent to requiring either \(a_1>a_2 \quad\text{or}\quad b_1<b_2,\) which is exactly the second condition of Theorem 2.8.

Similarly, let \(N(v)=[1,a_1]\cup[b_1,m],\; N(u)=[1,a_2]\cup[b_2,m].\) The complementary block of \(N(v)\) is \([a_1,b_1].\) For \(N(u)\) not to contain the complementary block of \(N(v)\), the interval \([a_1,b_1]\) must fail to lie entirely inside \(N(u)\). Since \(N(u)\) contains all vertices outside \((a_2,b_2)\), this is equivalent to requiring \(a_1<b_2\) and \(a_2<b_1.\) By symmetry, the same argument applies to the complementary block of \(N(u)\). Hence, neither neighborhood contains the complementary block of the other if and only if \(a_2<b_1 \; \text{and}\; a_1<b_2,\) which is exactly the third condition of Theorem 2.8. \(\square\)

For another equivalent characterization based on the circular ones property, we refer the reader to the relevant results presented in [10]. The existing literature regarding minimal forbidden induced subgraph characterizations of certain subclasses of split graphs forms the foundation for the results presented in this work. As a complete characterization of word-representable split graphs in terms of minimal forbidden induced subgraphs remains unknown, researchers have primarily focused on restricted subclasses to make progress. These restrictions typically include:

• bounding the degree of vertices in the independent set \(E\),

• fixing the size of the clique \(K\),

• fixing the size of the independent set \(E\).

Theorem 2.10. [7] Let \(S_n = (E_{n-m}, K_m)\) be a split graph with \(m \leq 3\). Then \(S_n\) is word-representable.

Lemma 2.11. [7] Let \(S_n = (E_{n-m}, K_m)\) be a split graph, and let \(S_{n+1}\) be a split graph obtained from \(S_n\) by one of the following operations:

• Adding a vertex of degree 0 to \(E_{n-m}\),

• Adding a vertex of degree 1 to \(E_{n-m}\),

• Duplicating (i.e., copying) a vertex from either \(E_{n-m}\) or \(K_m\), where the new vertex has the same neighborhood as the original.

Then \(S_n\) is word-representable if and only if \(S_{n+1}\) is word-representable.

Remark 2.12. As a direct consequence of the previous lemma, we restrict our attention to split graphs \(S_n = (E_{n-m}, K_m)\) satisfying the following properties:

• No two vertices in \(S_n\) share the same neighborhood, up to adjacency between the vertices themselves.

• At most one vertex in the clique \(K_m\) is not adjacent to any vertex in the independent set \(E_{n-m}\).

• Every vertex in \(E_{n-m}\) has degree at least two.

These structural simplifications significantly reduce redundancy and assist in the development of the following characterization results corresponding to the types of restrictions discussed above.

Theorem 2.13. [7] Let \(m \geq 1\) and \(S_n = (E_{n-m}, K_m)\) be a split graph, where each vertex in \(E_{n-m}\) has degree at most 2. Then \(S_n\) is word-representable if and only if it contains none of \(T_2\) (as shown in Figure 4), \(A_\ell\) (from Figure 6 of [7]) as induced subgraphs.

Theorem 2.14. [7] Let \(S_n = (E_{n-4}, K_4)\) be a split graph. Then \(S_n\) is word-representable if and only if it contains none of \(T_1, T_2, T_3 , T_4\) (as shown in Figure 4) as induced subgraphs.

Theorem 2.15. [2] Let \(S_n = (E_{n-5}, K_5)\) be a split graph. Then \(S_n\) is word-representable if and only if it contains none of \(T_1, T_2, \ldots, T_8\) (as shown in Figure 4), \(T_9\) (from Figure 3 of [2]) as induced subgraphs.

Theorem 2.16. [9] Let \(S_n = (E_3, K_{n-3})\) be a split graph. Then \(S_n\) is word-representable if and only if it contains none of \(T_1, T_2, T_3\) (as shown in Figure 4) as induced subgraphs.

3. Characterization of word-representable split graphs with an independent set of size four

In this section, we present a characterization of word-representable split graphs with an independent set of size four in terms of minimal forbidden induced subgraphs. Throughout the section, word-representability is established primarily by applying Theorem 2.9 together with suitable labelings of the clique vertices.

We use the notation \(v_1 > v_2\) to indicate that \(v_1\) is placed before \(v_2\) in a given labeling. Although Theorem 2.9 describes the labeling as a circular arrangement of vertices, for convenience, we represent such arrangements linearly. Thus, an expression of the form \(v_1 > v_2 > \cdots > v_m\) denotes the corresponding circular ordering of the clique vertices; see Figure 5 (right) for the correspondence between a given labeling and its circular arrangement.

Throughout this work, any split graph satisfies the conditions mentioned in Remark 2.12.

Lemma 3.1. The split graph \(D_1\) shown in Figure 4, is a minimal non-word-representable graph.

Proof. We first draw Figure 5, which is a schematic representation of the graph \(D_1\) as shown in Figure 4, where clique vertices lie on the circle and the independent-set vertices are positioned outside the circle. To demonstrate the minimality of this graph, we show that deleting any vertex from \(D_1\) yields a word-representable graph.

By symmetry, it suffices to consider only four deletion cases. The vertices \(y,z,w\) have pairwise disjoint neighborhoods of size two; the clique vertices \(2,4,6\) each have a unique distinct neighbor in the independent set; and the clique vertices \(1,3,5\) share the common neighbor \(x\), while the neighbor other than \(x\) is unique for each of \(1,3,5\). Deleting any one vertex from each of these three classes produces an induced subgraph isomorphic to that obtained by deleting any other vertex from the same class. Moreover, \(x\) is the only vertex in the independent set of degree three. Accordingly, it is enough to consider deletions of the representative vertices \(y\), \(2\), \(1\), and \(x\). We provide vertex labeling in each case that satisfies the conditions of Theorem 2.9. To verify that a given labeling satisfies the conditions of Theorem 2.9, we indicate the neighborhoods of vertices in \(E\) using curly brackets.

To prove that \(D_1\) is not word-representable, we proceed by contradiction. Assume that \(D_1\) is word-representable. By Theorem 2.9, the neighborhood of every vertex of degree 2 must consist of two consecutive vertices on the circle. In particular, the neighborhoods of the vertices \(y,z,w\) each form consecutive pairs on the circle, as illustrated in Figure 5. Under this assumption, we have \(N(x)=\{1,3,5\}\), that is, \(x\) is adjacent to exactly one vertex from each of the neighborhoods of \(y,z,w\). Consequently, \(N(x)\) cannot form a consecutive block on the circle. This contradicts Theorem 2.9, and therefore \(D_1\) is not word-representable. \(\square\)

Remark 3.2. The minimality and non-word-representability of \(T_1, T_2, \ldots, T_8\) are established in [2, 7]. Hence, any graph containing at least one of \(T_1, T_2, \ldots, T_8\) or \(D_1\) as an induced subgraph is not word-representable, by the hereditary nature of word-representable graphs.

Theorem 3.3. Let \(S_n = (E_4, K_{n-4})\) be a split graph. Then \(S_n\) is word-representable if and only if it contains none of \(T_1, T_2, \ldots, T_8, D_1\) (as shown in Figure 4) as induced subgraphs.

Before proceeding to the proof, we introduce some notations for simplicity.

• For any subset \(S \subseteq E\), we use \(v_S\) to denote a vertex in \(K\) whose neighborhood in \(E\) is exactly \(S\), that is, \(N(v_S) \cap E = S\). In particular, \(v_{\emptyset}\) denotes a vertex in \(K\) with no neighbors in \(E\).

• For a vertex \(v \in K\) and a subset \(S \subseteq E\), we define the neighborhood and degree of \(v\) with respect to \(S\) by \(N_S(v) = N(v) \cap S \quad \text{and} \quad d_S(v) = |N(v) \cap S|,\) where \(N(v)\) denotes the neighborhood of \(v\) in the graph. Thus, \(N_S(v)\) and \(d_S(v)\) denote, respectively, the set and the number of neighbors of \(v\) in \(S\).
  In particular, since \(|E|=4\) throughout this work, we have \(d_E(v) \leq 4\) for every vertex \(v \in K_{n-4}\).

Observation 3.4. According to the definition of the complementary block of the neighborhood of an independent-set vertex in Theorem 2.9, any vertex labeling containing \(v_{\phi}\) trivially satisfies the second condition of Theorem 2.9. Moreover, if \(v_{\phi}\) is absent, then the only vertex that can violate this condition is a vertex \(v\) whose neighborhood is of the form \(N(v)=[1,a]\cup[b,m], \; a<b,\) with respect to the labeling. Throughout this work, the labelings we construct contain at most one such vertex. We now give an explicit example to illustrate our notation together with a labeling: \[K: v_{\{a_0\}}>v_{\{a_0,a_1\}}>v_{\{a_1\}}>v_{\{a_1,a_2\}}> v_{\{a_2\}}>v_{\{a_0,a_2\}}>v_{\{a_0,a_3\}}.\]

This is an example of a labeling with independent-set vertices \(a_0,a_1,a_2,a_3\). Since the notation for each clique vertex explicitly records its neighborhood in \(E\), the neighborhoods of the vertices in \(E\) can be read directly from the labeling. For instance, the first two vertices together with the last one form \(N(a_0)\), while the second, third, and fourth vertices form \(N(a_1)\); the remaining neighborhoods are obtained similarly. In this notation, the consecutive-block property of these neighborhoods is also immediate from the labeling. Moreover, \(N(a_0)\) does not contain the complementary block of the neighborhood of any other independent-set vertex.

We now establish three lemmas that together reduce the overall problem space.

Theorem 3.5. Let \(S_n = (E_4, K_{n-4})\) be a split graph such that there exists a vertex \(v_1 \in K_{n-4}\) such that \(d_{E_4}(v_1) = 4\). Then \(S_n\) is word-representable if and only if it contains none of \(T_2, T_3, T_4\) as induced subgraphs.

Proof. In this case, the vertex \(v_1\) is a all-adjacent vertex. By Theorem 2.2, a graph \(G\) is word-representable if and only if the graph \(G \setminus v_1\) is a comparability graph. Furthermore, a complete characterization of split comparability graphs in terms of forbidden induced subgraphs is given in [3] (see Figure 1). Addition of a universal vertex to \(B_1\) yields the graph \(T_2\) (see Figure 6). Similarly, addition of a universal vertex to \(B_2\) and \(B_3\) yields the graphs \(T_3\) and \(T_4\), respectively. Therefore, \(T_2, T_3\) and \(T_4\) are precisely the minimal forbidden induced subgraphs in this case. \(\square\)

Lemma 3.6. Let \(S_n = (E_4, K_{n-4})\) be a split graph such that there exist at least three vertices \(v_1, v_2, v_3\in K_{n-4}\) such that \(d_{E_4}(v_1)=d_{E_4}(v_2)=d_{E_4}(v_3) = 3\), then \(S_n\) is not word-representable.

Proof. We consider a split graph shown in Figure 7, with vertices \(v_1, v_2, v_3\) satisfying \(d_{E_4}(v_1) =d_{E_4}(v_2) = d_{E_4}(v_3) = 3.\) As illustrated in the figure, this graph is isomorphic to the graph \(T_1\). Since \(T_1\) is not word-representable, every graph satisfying the hypothesis of the lemma is not word-representable. \(\square\)

As a result of the above lemma, a word-representable split graph with an independent set of size four, can contain at most two vertices in the clique such that their degree with respect to the independent set is three.

Lemma 3.7. Let \(S_n = (E_4, K_{n-4})\) be a split graph such that there exist at least five vertices \(v_1, v_2, v_3, v_4,\\ v_5\in K_{n-4}\) such that \(d_{E_4}(v_1)=d_{E_4}(v_2)=d_{E_4}(v_3)=d_{E_4}(v_4)=d_{E_4}(v_5) = 2\), then \(S_n\) is not word-representable.

Proof. As observed, the graph \(T_7\) (see Figure 4) satisfies the hypothesis of the lemma and is non-word-representable. Moreover, from the structure of \(T_7\), it follows that every graph satisfying the hypothesis of the lemma must contain \(T_7\) as an induced subgraph. Therefore, every graph arising in this case is not word-representable. \(\square\)

As a result of the above lemma, a word-representable split graph with an independent set of size four, can contain at most four vertices in the clique such that their degree with respect to the independent set is two.

Remark 3.8. Combining the above three lemmas, the overall problem space can be significantly reduced. Henceforth, we restrict our attention to split graphs of the form \(S_n = (E_4, K_{n-4})\), satisfying the following conditions:

• There is no vertex \(v \in K_{n-4}\) such that \(d_{E_4}(v) = 4\).

• There exist at most two vertices \(v_1, v_2 \in K_{n-4}\) with \(d_{E_4}(v_1) = d_{E_4}(v_2) = 3\).

• There exist at most four vertices \(v_1, v_2, v_3, v_4 \in K_{n-4}\) with \(d_{E_4}(v_1) = d_{E_4}(v_2) = d_{E_4}(v_3) = d_{E_4}(v_4) = 2\).

In the following, we prove three theorems, each established using a common proof strategy, which we briefly outline below.

Step 1. We begin by fixing a basic structural configuration (Figures 8 and 9) common to all split graphs satisfying the hypothesis of each theorem. Since the size of the independent set is fixed, we then consider all possible graph extensions (Definition 3.9) obtained by adding vertices to the clique in this configuration.

Step 2. To avoid redundancy, we classify independent-set vertices into different categories by the structural similarities of their neighborhoods and organize the problem space into non-isomorphic extension cases.

Step 3. Using straightforward structural observations, we discard all extensions that yield any of the graphs \(T_1, T_2, \ldots, T_8\) or \(D_1\) and list labelings of clique vertices of all possible word-representable extensions.

Definition 3.9. Let \(S_n=(E_{n-m},K_m)\) be a split graph and let \(i\ge 0\) be a fixed integer. For \(p\ge 1\), the graph \(S_{n+p}=(E_{n-m},K_{m+p})\) is called a \(p\)th \(i\)-degree extension of \(S_n\) if it is obtained from \(S_n\) by adding \(p\) new vertices \(v_1,v_2,\ldots,v_p\) to the clique \(K_m\) such that \(d_E(v_1)=d_E(v_2)=\cdots=d_E(v_p)=i.\) Each vertex \(v_j\) (\(1\le j\le p\)) is called an \(i\)-degree extension vertex.

For instance, by Lemma 3.7, a word-representable split graph with an independent set of size four contains at most four vertices in the clique whose degree with respect to the independent set is two. Therefore, in the following Theorems 3.11–3.13, it suffices to examine extensions containing at most four such vertices; that is, up to the fourth \(2\)-degree extension.

Definition 3.10. Let \(S_n = (E_{n-m}, K_{m})\) be a split graph. Let \(A=\{a_1,a_2,\ldots,a_i\}\subseteq E_{n-m}\) and \(B=\{b_1,b_2,\ldots,b_i\}\subseteq K_{m}\), where \(3\le i\le n-m\). We say that \(B\) exhibits a cyclic neighborhood pattern on \(A\) if \(N_A(b_j)=\{a_j,a_{j+1}\}\), for \(j\in \{1,2,\ldots,i-1\}\) and \(N_A(b_i)=\{a_1,a_i\}\).

For instance, when \(i=3\) or \(i=4\), this property is illustrated in Figure 10. In particular, addition of the vertex \(v_{\phi}\) to the left and right configurations yields the graphs \(T_1\) and \(T_5\), respectively.

Theorem 3.11. Let \(S_n = (E_4, K_{n-4})\) be a split graph satisfying the conditions of Remark 3.8 and no vertex \(v \in K_{n-4}\) such that \(d_{E_4}(v) = 3\). Then \(S_n\) is word-representable if and only if it contains none of \(T_1, T_5, D_1\) as induced subgraphs.

Proof. The necessary part of the proof follows directly from Remark 3.2.

For the sufficient part of the proof, let \(E_4 = \{a_i : 0 \le i \le 3\}\), where the indices are taken modulo \(4\). Since \(S_n\) satisfies the conditions of Remark 2.12, no two vertices in \(S_n\) have the same neighborhood. Moreover, there is no vertex \(v \in K_{n-4}\) with \(d_{E_4}(v)=3\). Hence, each vertex in \(K_{n-4}\) corresponds to a distinct subset of \(E_4\) of size at most two. It follows that \(K_{n-4}\) can contain at most \(11\) vertices, namely \[v_{\phi},\; v_{\{a_0\}},\; v_{\{a_1\}},\; v_{\{a_2\}},\; v_{\{a_3\}},\; v_{\{a_0,a_1\}},\; v_{\{a_0,a_2\}},\; v_{\{a_0,a_3\}},\; v_{\{a_1,a_2\}},\; v_{\{a_1,a_3\}},\; v_{\{a_2,a_3\}}.\] However, when \(S_n\) is word-representable, there are at most four vertices of degree two with respect to \(E_4\). We regard \(E_4\) as the basic underlying structure common to all \(S_n\) under this theorem, and any additional vertex introduced in the constructions below is treated as an extension vertex.

We first consider that \(S_n\) contains at least three 2-degree extension vertices. In the following, we present three observations that characterize those extensions which yield \(T_1\), \(T_5\), and \(D_1\) as induced subgraphs.

Obs. 1: If \(K\) contains vertices \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_{i+1},a_{i+2}\}},\; v_{\{a_i,a_{i+2}\}} \}\) that exhibit a cyclic neighborhood pattern on \(\{a_i,a_{i+1},a_{i+2}\}\) for some \(i \in \{0,1,2,3\}\), then addition of either \(v_{\phi}\) or \(v_{\{a_{i+3}\}}\) yields an induced subgraph isomorphic to \(T_1\).

Obs. 2: If \(K\) contains four vertices that exhibit a cyclic neighborhood pattern on \(E_4\), then addition of \(v_{\phi}\) yields an induced subgraph isomorphic to \(T_5\).

Obs. 3: If \(K\) contains vertices \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_{i},a_{i+2}\}},\; v_{\{a_{i},a_{i+3}\}} \}\) for some \(i \in \{0,1,2,3\}\), then addition of \(v_{\{a_{i+1}\}}, v_{\{a_{i+2}\}}\) and \(v_{\{a_{i+3}\}}\) yields an induced subgraph isomorphic to \(D_1\).

To analyze the overall problem space, we decompose it into three exhaustive cases, corresponding to the non-isomorphic configurations that arise when three 2-degree extension vertices are present.

In this setting, only three non-isomorphic configurations can occur (see Figure 11):

(i) in \(E_4\) all three vertices share a common neighbor (left);

(ii) in \(E_4\) no common neighbor is shared by all three, but every pair of vertices shares a common neighbor (middle); and

(iii) in \(E_4\) no common neighbor is shared by all three and there exists a pair of vertices that share no common neighbor (right).

These three possibilities exhaust all configurations in this setting, thereby establishing the completeness of the case decomposition.

In each case, after excluding the extensions ruled out by the preceding observations, we identify all possible word-representable extensions.

Case 1. \(K\) contains \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_i,a_{i+2}\}},\; v_{\{a_i,a_{i+3}\}} \}\) for some \(i \in \{0,1,2,3\}\).

Since the vertices \(v_{\{a_i,a_{i+1}\}},\; v_{\{a_i,a_{i+2}\}},\; v_{\{a_i,a_{i+3}\}}\) share a common neighbor \(a_i\), it follows from Obs. 3 that no word-representable extension can contain \(\{ v_{\{a_{i+1}\}}, v_{\{a_{i+2}\}}, v_{\{a_{i+3}\}} \}\). Thus, a word-representable extension may contain any of the following: \(\{ v_{\{a_i\}}, v_{\{a_{i+1}\}}, v_{\{a_{i+2}\}} \}\) or \(\{ v_{\{a_i\}}, v_{\{a_{i+1}\}}, v_{\{a_{i+3}\}} \}\) or \(\{ v_{\{a_i\}}, v_{\{a_{i+2}\}}, v_{\{a_{i+3}\}} \}.\)

\(\hookrightarrow\) Word-representable extensions containing \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_i,a_{i+2}\}},\; v_{\{a_i,a_{i+3}\}} \}\):

(i) \(K\): \(v_{\{a_{i+1}\}}>v_{\{a_i,a_{i+1}\}}> v_{\{a_{i}\}}> v_{\{a_{i},a_{i+3}\}}> v_{\{a_{i},a_{i+2}\}}> v_{\{a_{i+2}\}}>v_{\phi}\).

(ii) \(K\): \(v_{\{a_{i+1}\}}>v_{\{a_i,a_{i+1}\}}> v_{\{a_{i}\}}> v_{\{a_{i},a_{i+2}\}}> v_{\{a_{i},a_{i+3}\}}> v_{\{a_{i+3}\}}>v_{\phi}\).

(iii) \(K\): \(v_{\{a_{i+3}\}}>v_{\{a_i,a_{i+3}\}}> v_{\{a_{i}\}}> v_{\{a_{i},a_{i+1}\}}> v_{\{a_{i},a_{i+2}\}}> v_{\{a_{i+2}\}}>v_{\phi}\).

Further, if an additional 2-degree extension vertex is added, then by the requirement of having a unique neighborhood, it must be of the form \(v_{\{a_{i+1},a_{i+2}\}}\) or \(v_{\{a_{i+1},a_{i+3}\}}\) or \(v_{\{a_{i+2},a_{i+3}\}}\). Since each such vertex creates a cyclic neighborhood pattern together with the corresponding pair among \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_i,a_{i+2}\}} \},\; \{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_i,a_{i+3}\}} \},\; \{ v_{\{a_i,a_{i+2}\}},\; v_{\{a_i,a_{i+3}\}} \}\), we apply Obs. 1 to obtain all possible word-representable extensions below.

\(\hookrightarrow\) Word-representable extensions containing \(\{ v_{\{a_i,a_{i+1}\}}, v_{\{a_i,a_{i+2}\}}, v_{\{a_i,a_{i+3}\}},v_{\{a_{i+1},a_{i+2}\}}\}\):

(iv) \(K\): \(v_{\{a_i\}}>v_{\{a_i,a_{i+1}\}}> v_{\{a_{i+1}\}}> v_{\{a_{i+1},a_{i+2}\}}>v_{\{a_{i+2}\}}> v_{\{a_{i},a_{i+2}\}}> v_{\{a_{i},a_{i+3}\}}\).

\(\hookrightarrow\) Word-representable extensions containing \(\{ v_{\{a_i,a_{i+1}\}},v_{\{a_i,a_{i+2}\}},v_{\{a_i,a_{i+3}\}},v_{\{a_{i+1},a_{i+3}\}}\}\):

(v) \(K\): \(v_{\{a_i\}}>v_{\{a_i,a_{i+1}\}}> v_{\{a_{i+1}\}}> v_{\{a_{i+1},a_{i+3}\}}>v_{\{a_{i+3}\}}> v_{\{a_{i},a_{i+3}\}}> v_{\{a_{i},a_{i+2}\}}\).

\(\hookrightarrow\) Word-representable extensions containing \(\{ v_{\{a_i,a_{i+1}\}}, v_{\{a_i,a_{i+2}\}},v_{\{a_i,a_{i+3}\}},v_{\{a_{i+2},a_{i+3}\}}\}\):

(vi) \(K\): \(v_{\{a_i\}}>v_{\{a_i,a_{i+3}\}}> v_{\{a_{i+3}\}}> v_{\{a_{i+2},a_{i+3}\}}>v_{\{a_{i+2}\}}> v_{\{a_{i},a_{i+2}\}}> v_{\{a_{i},a_{i+1}\}}\).

Case 2. \(K\) contains \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_{i+1},a_{i+2}\}},\; v_{\{a_i,a_{i+2}\}}\}\) for some \(i \in \{0,1,2,3\}\).

Since the vertices \(\{ v_{\{a_i,a_{i+1}\}},v_{\{a_{i+1},a_{i+2}\}},v_{\{a_i,a_{i+2}\}} \},\) exhibit a cyclic neighborhood pattern on \(\{a_i,a_{i+1},a_{i+2}\}\), it follows from Obs. 1 that neither \(v_{\phi}\) nor \(v_{\{a_{i+3}\}}\) can be added.

Further, if an additional 2-degree extension vertex is added, then due to the requirement of having a unique neighborhood, it must be of the form \(v_{\{a_i,a_{i+3}\}}\) or \(v_{\{a_{i+1},a_{i+3}\}}\) or \(v_{\{a_{i+2},a_{i+3}\}}\). Below, we list all possible extensions that contain neither \(v_{\phi}\) nor \(v_{\{a_{i+3}\}}\).

\(\hookrightarrow\) Word-representable extension containing \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_{i+1},a_{i+2}\}},\; v_{\{a_i,a_{i+2}\}},v_{\{a_i,a_{i+3}\}}\}\):

(vii) \(K\): \(v_{\{a_i\}}>v_{\{a_i,a_{i+1}\}}> v_{\{a_{i+1}\}}> v_{\{a_{i+1},a_{i+2}\}}>v_{\{a_{i+2}\}}> v_{\{a_{i},a_{i+2}\}}> v_{\{a_{i},a_{i+3}\}}\).

\(\hookrightarrow\) Word-representable extension containing \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_{i+1},a_{i+2}\}},\; v_{\{a_i,a_{i+2}\}},v_{\{a_{i+1},a_{i+3}\}}\}\):

(viii) \(K\): \(v_{\{a_{i+1}\}}>v_{\{a_{i+1},a_{i+2}\}}> v_{\{a_{i+2}\}}> v_{\{a_{i},a_{i+2}\}}>v_{\{a_{i}\}}> v_{\{a_{i},a_{i+1}\}}> v_{\{a_{i+1},a_{i+3}\}}\).

\(\hookrightarrow\) Word-representable extension containing \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_{i+1},a_{i+2}\}},\; v_{\{a_i,a_{i+2}\}},v_{\{a_{i+2},a_{i+3}\}}\}\):

(ix) \(K\): \(v_{\{a_{i+2}\}}>v_{\{a_{i},a_{i+2}\}}> v_{\{a_{i}\}}> v_{\{a_{i},a_{i+1}\}}>v_{\{a_{i+1}\}}> v_{\{a_{i+1},a_{i+2}\}}> v_{\{a_{i+2},a_{i+3}\}}\).

Since the extensions listed in (vii)-(ix) exhaust all possibilities under the condition of Obs. 1, it follows that, by deleting the additional \(2\)-degree extension vertex from each of these extensions, we obtain all possible word-representable extensions containing exactly three \(2\)-degree extension vertices in this case.

Case 3. \(K\) contains the vertices \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_{i+1},a_{i+2}\}},\; v_{\{a_{i+2},a_{i+3}\}} \}\) for some \(i \in \{0,1,2,3\}\).

\(\hookrightarrow\) Word-representable extension containing \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_{i+1},a_{i+2}\}},\; v_{\{a_{i+2},a_{i+3}\}} \}\):

(x) \(K\): \(v_{\{a_i\}}>v_{\{a_i,a_{i+1}\}}> v_{\{a_{i+1}\}}> v_{\{a_{i+1},a_{i+2}\}}>v_{\{a_{i+2}\}}> v_{\{a_{i+2},a_{i+3}\}}> v_{\{a_{i+3}\}}>v_{\phi}\).

Further, if an additional 2-degree extension vertex is added, then by the requirement of having a unique neighborhood, it must be of the form \(v_{\{a_{i},a_{i+2}\}}\) or \(v_{\{a_{i+1},a_{i+3}\}}\) or \(v_{\{a_{i},a_{i+3}\}}\). Since each such vertex creates a cyclic neighborhood pattern together with the corresponding pair among \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_{i+1},a_{i+2}\}} \},\\ \{ v_{\{a_{i+1},a_{i+2}\}},\; v_{\{a_{i+2},a_{i+3}\}} \}, \{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_{i+1},a_{i+2}\}},\; v_{\{a_{i+2},a_{i+3}\}} \}\), we apply Obs. 1 and 2 to obtain all possible word-representable extensions below.

\(\hookrightarrow\) Word-representable extension containing \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_{i+1},a_{i+2}\}},\; v_{\{a_{i+2},a_{i+3}\}},v_{\{a_{i},a_{i+2}\}} \}\):

(xi) \(K\): \(v_{\{a_i\}}>v_{\{a_i,a_{i+1}\}}> v_{\{a_{i+1}\}}> v_{\{a_{i+1},a_{i+2}\}}>v_{\{a_{i+2}\}}> v_{\{a_{i+2},a_{i+3}\}}> v_{\{a_{i},a_{i+2}\}}\).

\(\hookrightarrow\) Word-representable extension containing \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_{i+1},a_{i+2}\}},\; v_{\{a_{i+2},a_{i+3}\}},v_{\{a_{i+1},a_{i+3}\}} \}\):

(xii) \(K\): \(v_{\{a_{i+1}\}}>v_{\{a_{i+1},a_{i+2}\}}> v_{\{a_{i+2}\}}> v_{\{a_{i+2},a_{i+3}\}}>v_{\{a_{i+3}\}}> v_{\{a_{i+1},a_{i+3}\}}> v_{\{a_{i},a_{i+1}\}}\).

\(\hookrightarrow\) Word-representable extension containing \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_{i+1},a_{i+2}\}},\; v_{\{a_{i+2},a_{i+3}\}},v_{\{a_{i},a_{i+3}\}} \}\):

(xiii) \(K\): \(v_{\{a_i\}}>v_{\{a_i,a_{i+1}\}}> v_{\{a_{i+1}\}}> v_{\{a_{i+1},a_{i+2}\}}>v_{\{a_{i+2}\}}> v_{\{a_{i+2},a_{i+3}\}}>v_{\{a_{i+3}\}}>v_{\{a_{i},a_{i+3}\}}\).

We observe that if \(S_n\) contains at most two \(2\)-degree extension vertices, then any such pair has, up to isomorphism, only two possible forms: \(\{v_{\{a_i,a_{i+1}\}}, v_{\{a_{i+1},a_{i+2}\}}\}\) for some \(i\in\{0,1,2,3\}\), that is, the two vertices share a common neighbor in \(E_4\); or \(\{v_{\{a_i,a_{i+1}\}}, v_{\{a_{i+2},a_{i+3}\}}\}\) for some \(i\in\{0,1,2,3\}\), that is, they do not share a common neighbor.

Now observe that the extension (x) contains \(\{v_{\{a_i,a_{i+1}\}},\; v_{\{a_{i+1},a_{i+2}\}},\; v_{\{a_{i+2},a_{i+3}\}}\},\) and hence realizes both types of pairs simultaneously, together with all \(1\)-degree extension vertices and \(v_{\phi}\). Consequently, every graph arising in this theorem with at most two 2-degree extension vertices is an induced subgraph of the graph determined by the clique labeling in (x) together with \(E_4\) and therefore word-representable.

This completes the proof. \(\square\)

Theorem 3.12. Let \(S_n = (E_4, K_{n-4})\) be a split graph satisfying the conditions of Remark 3.8 and there exists exactly one vertex \(v \in K_{n-4}\) with \(d_{E_4}(v) = 3\). Then \(S_n\) is word-representable if and only if it contains none of \(T_1, T_2, T_3, T_5\) as induced subgraphs.

Proof. The necessary part of the proof follows directly from Remark 3.2.

For the sufficient part of the proof, let \(E_4 = \{a_0,a_1,a_2,b\}\). Throughout the proof, the indices of the vertices in Category-A are taken modulo \(3\). Since \(S_n\) satisfies the conditions of Remark 2.12, no two vertices in \(S_n\) have the same neighborhood. Moreover, there is exactly one vertex \(v \in K_{n-4}\) with \(d_{E_4}(v)=3\). Hence, each vertex, except \(v\) in \(K_{n-4}\) corresponds to a distinct subset of \(E\) of size at most two. It follows that \(K_{n-4}\) can contain at most \(12\) vertices, namely \[v_{\phi},\; v_{\{a_0\}},\; v_{\{a_1\}},\; v_{\{a_2\}},\; v_{\{b\}},\; v_{\{a_0,a_1\}},\; v_{\{a_0,a_2\}},\; v_{\{a_1,a_2\}},\; v_{\{a_0,b\}},\; v_{\{a_1,b\}},\; v_{\{a_2,b\}},\; v_{\{a_0,a_{1},a_{2}\}}.\]However, in a word-representable graph \(S_n\), there are at most four vertices of degree two with respect to \(E_4\). We regard the graph in Figure 8 as the basic underlying structure common to all \(S_n\) under this theorem, and any additional vertex introduced in the constructions below is treated as an extension vertex. In the following, we give six observations that identify the graph extensions yielding \(T_1, T_2, T_3, T_5\) as induced subgraphs.

Obs. 1: If \(K\) contains \(\{ v_{\{a_i,b\}},v_{\{a_{i+1},b\}}\}\) for some \(i \in \{0,1,2\}\), then addition of \(v_{\{a_{i+2}\}}\) or \(v_{\phi}\) yields an induced subgraph isomorphic to \(T_2\) or \(T_1\) respectively.

Obs. 2: If \(K\) contains \(\{ v_{\{a_0\}},\; v_{\{a_{1}\}},\; v_{\{a_2\}} \}\), then it has an induced subgraph isomorphic to \(T_2\).

Obs. 3: If \(K\) contains \(v_{\{a_i,b\}}\) for some \(i \in \{0,1,2\}\), then addition of \(v_{\{a_{i+1}\}}\) and \(v_{\{a_{i+2}\}}\) yields an induced subgraph isomorphic to \(T_2\).

Obs. 4: If \(K\) contains \(\{ v_{\{a_0,b\}},\; v_{\{a_{1},b\}},\; v_{\{a_{2},b\}} \}\), then it has an induced subgraph isomorphic to \(T_2\).

Obs. 5: If \(K\) contains \(\{ v_{\{a_i,a_{i+1}\}},v_{\{a_{i+1},a_{i+2}\}},v_{\{a_{i},a_{i+2}\}} \}\) that exhibit a cyclic neighborhood pattern on \(\{a_i,a_{i+1},a_{i+2}\}\) for some \(i \in \{0,1,2\}\), then it has an induced subgraph isomorphic to \(T_3\).

Obs. 6: If \(K\) contains four vertices that exhibit a cyclic neighborhood pattern on \(E_4\), then addition of \(v_{\phi}\) yields an induced subgraph isomorphic to \(T_5\).

As a consequence of Obs. 2, a word-representable extension cannot contain \(\{v_{\{a_i\}}, v_{\{a_{i+1}\}},\\ v_{\{a_{i+2}\}}\}\) for \(i\in \{0,1,2\}\). We use this observation repeatedly throughout the proof to determine all possible word-representable extensions.

We first consider that \(S_n\) contains at least two \(2\)-degree extension vertices. Up to isomorphism, such pairs give rise to only four possible configurations (see Figure 12):

(i) they share a common neighbor, and all their neighbors lie in Category-A;

(ii) they share a common neighbor in Category-A, and at least one of them has a neighbor in Category-B;

(iii) they share a common neighbor in Category-B; and

(iv) they do not share any common neighbor in \(E_4\).

Since Category-A contains three vertices and Category-B contains a single vertex, these four cases exhaust all possible configurations, thereby establishing the completeness of the case decomposition.

In each case, after excluding the extensions ruled out by the preceding observations, we identify all possible word-representable extensions.

Case 1: \(K\) contains \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_{i+1},a_{i+2}\}}\}\) for some \(i \in \{0,1,2\}\).

Since, by Obs. 5, \(v_{\{a_i,a_{i+2}\}}\) cannot be added, if an additional 2-degree extension vertex is added, then it must be of the form \(v_{\{a_i,b\}}\) or \(v_{\{a_{i+1},b\}}\) or \(v_{\{a_{i+2},b\}}\). We then apply Obs. 3 to obtain all word-representable extensions listed below.

\(\hookrightarrow\) Word-representtable extensions containing \(\{ v_{\{a_i,a_{i+1}\}}, v_{\{a_{i+1},a_{i+2}\}},v_{\{a_i,b\}}\}\):

(i)\(K\): \(v_{\{b\}}>v_{\{a_{i}, b\}}> v_{\{a_{i}\}}> v_{\{a_{i},a_{i+1}\}}>v_{\{a_i,a_{i+1},a_{i+2}\}}>v_{\{a_{i+1},a_{i+2}\}}> v_{\{a_{i+1}\}}> v_{\phi}\).

(ii) \(K\): \(v_{\{b\}}>v_{\{a_{i}, b\}}> v_{\{a_{i}\}}> v_{\{a_{i},a_{i+1}\}}>v_{\{a_i,a_{i+1},a_{i+2}\}}>v_{\{a_{i+1},a_{i+2}\}}> v_{\{a_{i+2}\}}> v_{\phi}\).

\(\hookrightarrow\) Word-representtable extensions containing \(\{ v_{\{a_i,a_{i+1}\}}, v_{\{a_{i+1},a_{i+2}\}},v_{\{a_{i+1},b\}}\}\):

(iii) \(K\): \(v_{\{b\}}>v_{\{a_{i+1}, b\}}> v_{\{a_{i+1}\}}> v_{\{a_{i},a_{i+1}\}}>v_{\{a_i,a_{i+1},a_{i+2}\}}>v_{\{a_{i+1},a_{i+2}\}}> v_{\{a_{i+2}\}}> v_{\phi}\).

(iv) \(K\): \(v_{\{a_i\}}>v_{\{a_i,a_{i+1}\}}> v_{\{a_i,a_{i+1},a_{i+2}\}}> v_{\{a_{i+1},a_{i+2}\}}>v_{\{a_{i+1}\}}> v_{\{a_{i+1},b\}}> v_{\{b\}}> v_{\phi}\).

\(\hookrightarrow\) Word-representtable extensions containing \(\{ v_{\{a_i,a_{i+1}\}}, v_{\{a_{i+1},a_{i+2}\}},v_{\{a_{i+2},b\}}\}\):

(v) \(K\): \(v_{\{a_i\}}>v_{\{a_i,a_{i+1}\}}> v_{\{a_i,a_{i+1},a_{i+2}\}}> v_{\{a_{i+1},a_{i+2}\}}>v_{\{a_{i+2}\}}> v_{\{a_{i+2},b\}}> v_{\{b\}}> v_{\phi}\).

(vi) \(K\): \(v_{\{a_{i+1}\}}>v_{\{a_i,a_{i+1}\}}> v_{\{a_i,a_{i+1},a_{i+2}\}}> v_{\{a_{i+1},a_{i+2}\}}>v_{\{a_{i+2}\}}> v_{\{a_{i+2},b\}}> v_{\{b\}}> v_{\phi}\).

Note that the extensions listed in (i)-(iii) realize all possible combinations of three \(1\)-degree extension vertices together with \(v_{\phi}\), except for \(\{v_{\{a_i\}}, v_{\{a_{i+1}\}}, v_{\{a_{i+2}\}}\}\), which is excluded by Obs. 2. Consequently, by deleting the additional \(2\)-degree extension vertex from each of these extensions, we obtain all possible word-representable extensions containing exactly two \(2\)-degree extension vertices in this case.

Since the inclusion of \(v_{\{a_i,a_{i+2}\}}\) is excluded by Obs. 5, if two additional 2-degree extension vertices are added, the possible pairs are \(\{v_{\{a_i,b\}},v_{\{a_{i+1},b\}}\}\) or \(\{v_{\{a_i,b\}},v_{\{a_{i+2},b\}}\}\) or \(\{v_{\{a_{i+1},b\}},v_{\{a_{i+2},b\}}\}\). We then apply Obs. 1 to obtain all word-representable extensions listed below.

\(\hookrightarrow\) Word-representtable extension containing \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_{i+1},a_{i+2}\}},v_{\{a_i,b\}},v_{\{a_{i+1},b\}}\}\):

(vii) \(K\): \(v_{\{b\}}>v_{\{a_{i}, b\}}> v_{\{a_{i}\}}> v_{\{a_{i},a_{i+1}\}}>v_{\{a_i,a_{i+1},a_{i+2}\}}> v_{\{a_{i+1},a_{i+2}\}}> v_{\{a_{i+1}\}}> v_{\{a_{i+1}, b\}}\).

\(\hookrightarrow\) Word-representtable extension containing \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_{i+1},a_{i+2}\}},v_{\{a_i,b\}},v_{\{a_{i+2},b\}}\}\):

(viii) \(K\): \(v_{\{b\}}>v_{\{a_{i}, b\}}> v_{\{a_{i}\}}> v_{\{a_{i},a_{i+1}\}}>v_{\{a_i,a_{i+1},a_{i+2}\}}> v_{\{a_{i+1},a_{i+2}\}}> v_{\{a_{i+2}\}}> v_{\{a_{i+2}, b\}}\).

\(\hookrightarrow\) Word-representtable extension containing \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_{i+1},a_{i+2}\}},v_{\{a_{i+1},b\}},v_{\{a_{i+2},b\}}\}\):

(ix) \(K\): \(v_{\{b\}}>v_{\{a_{i+1}, b\}}> v_{\{a_{i+1}\}}> v_{\{a_{i},a_{i+1}\}}>v_{\{a_i,a_{i+1},a_{i+2}\}}> v_{\{a_{i+1},a_{i+2}\}}> v_{\{a_{i+2}\}}> v_{\{a_{i+2}, b\}}\).

Case 2: \(K\) contains \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_{i+1},b\}}\}\) for some \(i \in \{0,1,2\}\).

By Obs. 3, \(\{ v_{\{a_{i}\}},v_{\{a_{i+2}\}} \}\) cannot be added.

If an additional \(2\)-degree extension vertex is added, then it must be of the form \(v_{\{a_i,a_{i+2}\}}\) or \(v_{\{a_{i+1},a_{i+2}\}}\) or \(v_{\{a_i,b\}}\) or \(v_{\{a_{i+2},b\}}\). For the first two possibilities, we apply Obs. 3, while for the latter two we apply Obs. 1, to obtain all word-representable extensions listed below.

\(\hookrightarrow\) Word-representable extensions containing \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_{i+1},b\}},v_{\{a_i,a_{i+2}\}}\}\):

(x) \(K\): \(v_{\{a_i\}}>v_{\{a_i,a_{i+2}\}}> v_{\{a_i,a_{i+1},a_{i+2}\}}> v_{\{a_{i},a_{i+1}\}}>v_{\{a_{i+1}\}}> v_{\{a_{i+1},b\}}> v_{\{b\}}> v_{\phi}\).

(xi) \(K\): \(v_{\{a_{i+2}\}}>v_{\{a_i,a_{i+2}\}}> v_{\{a_i,a_{i+1},a_{i+2}\}}> v_{\{a_{i},a_{i+1}\}}>v_{\{a_{i+1}\}}> v_{\{a_{i+1},b\}}> v_{\{b\}}> v_{\phi}\).

\(\hookrightarrow\) Word-representable extensions containing \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_{i+1},b\}},v_{\{a_{i+1},a_{i+2}\}}\}\):

(xii) \(K\): \(v_{\{a_i\}}>v_{\{a_i,a_{i+1}\}}> v_{\{a_i,a_{i+1},a_{i+2}\}}> v_{\{a_{i+1},a_{i+2}\}}>v_{\{a_{i+1}\}}> v_{\{a_{i+1},b\}}> v_{\{b\}}> v_{\phi}\).

(xiii) \(K\): \(v_{\{a_{i+2}\}}>v_{\{a_{i+1},a_{i+2}\}}> v_{\{a_i,a_{i+1},a_{i+2}\}}> v_{\{a_{i},a_{i+1}\}}>v_{\{a_{i+1}\}}> v_{\{a_{i+1},b\}}> v_{\{b\}}> v_{\phi}\).

\(\hookrightarrow\) Word-representable extension containing \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_{i+1},b\}},v_{\{a_i,b\}}\}\):

(xiv) \(K\): \(v_{\{b\}}>v_{\{a_{i}, b\}}> v_{\{a_{i}\}}>v_{\{a_i,a_{i+1},a_{i+2}\}}> v_{\{a_{i},a_{i+1}\}}> v_{\{a_{i+1}\}}> v_{\{a_{i+1},b\}}\).

\(\hookrightarrow\) Word-representable extension containing \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_{i+1},b\}},v_{\{a_{i+2},b\}}\}\):

(xv) \(K\): \(v_{\{b\}}>v_{\{a_{i+2}, b\}}> v_{\{a_{i+2}\}}>v_{\{a_i,a_{i+1},a_{i+2}\}}> v_{\{a_{i},a_{i+1}\}}> v_{\{a_{i+1}\}}> v_{\{a_{i+1},b\}}\).

Note that the extensions listed in (x)-(xi) realize all possible combinations of three \(1\)-degree extension vertices together with \(v_{\phi}\), subject to the exclusion of \(\{v_{\{a_i\}}, v_{\{a_{i+2}\}}\}\) by Obs. 3. Consequently, by deleting the additional \(2\)-degree extension vertex from each of these extensions, we obtain all possible word-representable extensions containing exactly two \(2\)-degree extension vertices in this case.

Since the inclusion of \(\{v_{\{a_i,a_{i+2}\}},v_{\{a_{i+1},a_{i+2}\}}\}\) and \(\{v_{\{a_i,b\}},v_{\{a_{i+2},b\}}\}\) is excluded by Obs. 5 and Obs. 4, respectively, if two additional \(2\)-degree extension vertices are added, the possible pairs are \(\{v_{\{a_i,b\}},v_{\{a_{i+1},a_{i+2}\}}\}\) or \(\{v_{\{a_i,b\}},v_{\{a_i,a_{i+2}\}}\}\) or \(\{v_{\{a_{i+2},b\}},v_{\{a_{i+1},a_{i+2}\}}\}\) or \(\{v_{\{a_{i+2},b\}},\\v_{\{a_i,a_{i+2}\}}\}\). We then apply Obs. 1 to obtain all word-representable extensions listed below.

\(\hookrightarrow\) Word-representable extension containing \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_{i+1},b\}},v_{\{a_i,b\}},v_{\{a_{i+1},a_{i+2}\}}\}\):

(xvi) \(K\): \(v_{\{b\}}>v_{\{a_{i}, b\}}> v_{\{a_{i}\}}> v_{\{a_{i},a_{i+1}\}}>v_{\{a_i,a_{i+1},a_{i+2}\}}> v_{\{a_{i+1},a_{i+2}\}}> v_{\{a_{i+1}\}}> v_{\{a_{i+1}, b\}}\).

\(\hookrightarrow\) Word-representable extension containing \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_{i+1},b\}},v_{\{a_i,b\}},v_{\{a_{i},a_{i+2}\}}\}\):

(xvii) \(K\): \(v_{\{b\}}>v_{\{a_{i}, b\}}> v_{\{a_{i}\}}> v_{\{a_{i},a_{i+2}\}}>v_{\{a_i,a_{i+1},a_{i+2}\}}> v_{\{a_{i},a_{i+1}\}}> v_{\{a_{i+1}\}}> v_{\{a_{i+1}, b\}}\).

\(\hookrightarrow\) Word-representable extension containing \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_{i+1},b\}},v_{\{a_{i+2},b\}},v_{\{a_{i+1},a_{i+2}\}}\}\):

(xviii) \(K\): \(v_{\{a_{i+1}\}}>v_{\{ a_i,a_{i+1}\}}> v_{\{a_i,a_{i+1},a_{i+2}\}}> v_{\{a_{i+1},a_{i+2}\}}> v_{\{a_{i+2}\}}> v_{\{a_{i+2},b\}}> v_{\{b\}}> v_{\{a_{i+1}, b\}}\).

\(\hookrightarrow\) Word-representable extension containing \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_{i+1},b\}},v_{\{a_{i+2},b\}},v_{\{a_{i},a_{i+2}\}}\}\):

(xix) \(K\): \(v_{\{a_{i+1}\}}>v_{\{ a_i,a_{i+1}\}}> v_{\{a_i,a_{i+1},a_{i+2}\}}> v_{\{a_{i},a_{i+2}\}}> v_{\{a_{i+2}\}}> v_{\{a_{i+2},b\}}> v_{\{b\}}> v_{\{a_{i+1}, b\}}\).

Case 3: \(K\) contains \(\{ v_{\{a_i,b\}},\; v_{\{a_{i+1},b\}}\}\) for some \(i \in \{0,1,2\}\).

By Obs. 1, neither \(v_{\{a_{i+2}\}}\) nor \(v_{\phi}\) can be added.

Since the inclusion of \(v_{\{a_{i+2},b\}}\) is excluded by Obs. 4, if an additional \(2\)-degree extension vertex is added, then it must be of the form \(v_{\{a_i,a_{i+1}\}}\) or \(v_{\{a_{i+1},a_{i+2}\}}\) or \(v_{\{a_i,a_{i+2}\}}\). If two additional \(2\)-degree extension vertices are added, then the possible pairs are \(\{v_{\{a_i,a_{i+1}\}},v_{\{a_{i+1},a_{i+2}\}}\}\) or \(\{v_{\{a_i,a_{i+1}\}},v_{\{a_i,a_{i+2}\}}\}\) or \(\{v_{\{a_{i+1},a_{i+2}\}},v_{\{a_i,a_{i+2}\}}\}\). Below, we list all possible extensions that contain neither \(v_{\{a_{i+2}\}}\) nor \(v_{\phi}\).

\(\hookrightarrow\) Word-representable extension containing \(\{ v_{\{a_i,b\}},\; v_{\{a_{i+1},b\}},v_{\{a_i,a_{i+1}\}},v_{\{a_{i+1},a_{i+2}\}}\}\):

(xx) \(K\): \(v_{\{b\}}>v_{\{a_{i}, b\}}> v_{\{a_{i}\}}> v_{\{a_{i},a_{i+1}\}}>v_{\{a_i,a_{i+1},a_{i+2}\}}>v_{\{a_{i+1},a_{i+2}\}}> v_{\{a_{i+1}\}}> v_{\{a_{i+1},b\}}\).

\(\hookrightarrow\) Word-representable extension containing \(\{ v_{\{a_i,b\}},\; v_{\{a_{i+1},b\}},v_{\{a_i,a_{i+1}\}},v_{\{a_{i},a_{i+2}\}}\}\):

(xxi) \(K\): \(v_{\{b\}}>v_{\{a_{i}, b\}}> v_{\{a_{i}\}}> v_{\{a_{i},a_{i+2}\}}>v_{\{a_i,a_{i+1},a_{i+2}\}}>v_{\{a_{i},a_{i+1}\}}> v_{\{a_{i+1}\}}> v_{\{a_{i+1},b\}}\).

\(\hookrightarrow\) Word-representable extension containing \(\{ v_{\{a_i,b\}},\; v_{\{a_{i+1},b\}},v_{\{a_{i+1},a_{i+2}\}},v_{\{a_i,a_{i+2}\}}\}\):

(xxii) \(K\): \(v_{\{b\}}>v_{\{a_{i}, b\}}> v_{\{a_{i}\}}> v_{\{a_{i},a_{i+2}\}}>v_{\{a_i,a_{i+1},a_{i+2}\}}>v_{\{a_{i+1},a_{i+2}\}}> v_{\{a_{i+1}\}}> v_{\{a_{i+1},b\}}\).

Since the extensions listed in (xx)-(xxii) exhaust all possibilities under the condition of Obs. 1, it follows that, by deleting the two additional \(2\)-degree extension vertices and one of them, respectively, from each of these extensions, we obtain all possible word-representable extensions containing exactly two and three \(2\)-degree extension vertices in this case.

Case 4: \(K\) contains \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{a_{i+2},b\}}\}\) for some \(i \in \{0,1,2\}\).

This case is very much similar to Case 2. We use a similar argument to obtain all possible word-representable extensions below.

\(\hookrightarrow\) Word-representable extensions containing \(\{ v_{\{a_i,a_{i+1}\}}, v_{\{a_{i+2},b\}}, v_{\{a_{i},a_{i+2}\}}\}\):

(xxiii) \(K\): \(v_{\{b\}}>v_{\{a_{i+2}, b\}}> v_{\{a_{i+2}\}}> v_{\{a_{i},a_{i+2}\}}>v_{\{a_i,a_{i+1},a_{i+2}\}}>v_{\{a_{i},a_{i+1}\}}> v_{\{a_{i+1}\}}> v_{\phi}\).

(xxiv) \(K\): \(v_{\{b\}}>v_{\{a_{i+2}, b\}}> v_{\{a_{i+2}\}}> v_{\{a_{i},a_{i+2}\}}>v_{\{a_i,a_{i+1},a_{i+2}\}}>v_{\{a_{i},a_{i+1}\}}> v_{\{a_{i}\}}> v_{\phi}\).

\(\hookrightarrow\) Word-representable extensions containing \(\{ v_{\{a_i,a_{i+1}\}}, v_{\{a_{i+2},b\}}, v_{\{a_{i+1},a_{i+2}\}}\}\):

(xxv) \(K\): \(v_{\{b\}}>v_{\{a_{i+2}, b\}}> v_{\{a_{i+2}\}}> v_{\{a_{i+1},a_{i+2}\}}>v_{\{a_i,a_{i+1},a_{i+2}\}}>v_{\{a_{i},a_{i+1}\}}> v_{\{a_{i+1}\}}> v_{\phi}\).

(xxvi) \(K\): \(v_{\{b\}}>v_{\{a_{i+2}, b\}}> v_{\{a_{i+2}\}}> v_{\{a_{i+1},a_{i+2}\}}>v_{\{a_i,a_{i+1},a_{i+2}\}}>v_{\{a_{i},a_{i+1}\}}> v_{\{a_{i}\}}> v_{\phi}\).

\(\hookrightarrow\) Word-representable extension containing \(\{ v_{\{a_i,a_{i+1}\}}, v_{\{a_{i+2},b\}}, v_{\{a_{i},b\}}\}\):

(xxvii) \(K\): \(v_{\{b\}}>v_{\{a_{i+2}, b\}}> v_{\{a_{i+2}\}}>v_{\{a_i,a_{i+1},a_{i+2}\}}> v_{\{a_{i},a_{i+1}\}}> v_{\{a_{i}\}}> v_{\{a_{i},b\}}\).

\(\hookrightarrow\) Word-representable extension containing \(\{ v_{\{a_i,a_{i+1}\}}, v_{\{a_{i+2},b\}}, v_{\{a_{i+1},b\}}\}\):

(xxviii) \(K\): \(v_{\{b\}}>v_{\{a_{i+2}, b\}}> v_{\{a_{i+2}\}}>v_{\{a_i,a_{i+1},a_{i+2}\}}> v_{\{a_{i},a_{i+1}\}}> v_{\{a_{i+1}\}}> v_{\{a_{i+1},b\}}\).

\(\hookrightarrow\) Word-representable extension containing \(\{ v_{\{a_i,a_{i+1}\}}, v_{\{a_{i+2},b\}}, v_{\{a_{i},b\}},v_{\{a_{i+1},a_{i+2}\}}\}\):

(xxix) \(K\): \(v_{\{b\}}>v_{\{a_{i}, b\}}> v_{\{a_{i}\}}> v_{\{a_{i},a_{i+1}\}}>v_{\{a_i,a_{i+1},a_{i+2}\}}>v_{\{a_{i+1},a_{i+2}\}}> v_{\{a_{i+2}\}}> v_{\{a_{i+2},b\}}\).

\(\hookrightarrow\) Word-representable extension containing \(\{ v_{\{a_i,a_{i+1}\}}, v_{\{a_{i+2},b\}}, v_{\{a_{i},b\}},v_{\{a_{i},a_{i+2}\}}\}\):

(xxx) \(K\): \(v_{\{b\}}>v_{\{a_{i}, b\}}> v_{\{a_{i}\}}> v_{\{a_{i},a_{i+1}\}}>v_{\{a_i,a_{i+1},a_{i+2}\}}>v_{\{a_{i},a_{i+2}\}}> v_{\{a_{i+2}\}}> v_{\{a_{i+2},b\}}\).

\(\hookrightarrow\) Word-representable extension containing \(\{ v_{\{a_i,a_{i+1}\}}, v_{\{a_{i+2},b\}}, v_{\{a_{i+1},b\}},v_{\{a_{i+1},a_{i+2}\}}\}\):

(xxxi) \(K\): \(v_{\{b\}}>v_{\{a_{i+1}, b\}}> v_{\{a_{i+1}\}}> v_{\{a_{i},a_{i+1}\}}>v_{\{a_i,a_{i+1},a_{i+2}\}}>v_{\{a_{i+1},a_{i+2}\}}> v_{\{a_{i+2}\}}> v_{\{a_{i+2},b\}}\).

\(\hookrightarrow\) Word-representable extension containing \(\{ v_{\{a_i,a_{i+1}\}}, v_{\{a_{i+2},b\}}, v_{\{a_{i+1},b\}},v_{\{a_{i},a_{i+2}\}}\}\):

(xxxii) \(K\): \(v_{\{b\}}>v_{\{a_{i+1}, b\}}> v_{\{a_{i+1}\}}> v_{\{a_{i},a_{i+1}\}}>v_{\{a_i,a_{i+1},a_{i+2}\}}>v_{\{a_{i},a_{i+2}\}}> v_{\{a_{i+2}\}}> v_{\{a_{i+2},b\}}\).

Note that the extensions listed in (xxiii)-(xxiv) realize all possible combinations of three \(1\)-degree extension vertices together with \(v_{\phi}\), subject to the exclusion of \(\{v_{\{a_i\}}, v_{\{a_{i+1}\}}\}\) by Obs. 3. Consequently, by deleting the additional \(2\)-degree extension vertex from each of these extensions, we obtain all possible word-representable extensions containing exactly two \(2\)-degree extension vertices in this case.

We observe that if \(S_n\) contains at most one \(2\)-degree extension vertex, then any such vertex has, up to isomorphism, only two possible forms: \(v_{\{a_i,a_{i+1}\}}\) for some \(i\in\{0,1,2\}\), that is, both of its neighbors in \(E_4\) belong to Category-A; or \(v_{\{a_i,b\}}\) for some \(i\in\{0,1,2\}\), that is, one of its neighbors is the vertex \(b\).

If \(v_{\{a_i,b\}}\) is present, then by Obs. 3, \(\{ v_{\{a_{i+1}\}}\), \(v_{\{a_{i+2}\}} \}\) cannot be added.

Note that the extensions listed in (i)-(iii) realize all possible combinations of three \(1\)-degree extension vertices together with \(v_{\phi}\), except for \(\{v_{\{a_i\}}, v_{\{a_{i+1}\}}, v_{\{a_{i+2}\}}\}\), which is excluded by Obs. 2. Consequently, by deleting all \(2\)-degree extension vertices other than \(v_{\{a_i,a_{i+1}\}}\) from these extensions, we obtain all possible word-representable extensions containing at most one \(2\)-degree extension vertex, namely \(v_{\{a_i,a_{i+1}\}}\).

Similarly, the extensions listed in (i)-(ii) realize all possible combinations of three \(1\)-degree extension vertices together with \(v_{\phi}\), subject to the exclusion of \(\{v_{\{a_{i+1}\}}, v_{\{a_{i+2}\}}\}\) by Obs. 3. Consequently, by deleting all \(2\)-degree extension vertices other than \(v_{\{a_i,b\}}\) from these extensions, we obtain all possible word-representable extensions containing at most one \(2\)-degree extension vertex, namely \(v_{\{a_i,b\}}\).

This completes the proof. \(\square\)

Theorem 3.13. Let \(S_n = (E_4, K_{n-4})\) be a split graph satisfying the conditions of Remark 3.8 and there exist exactly two vertices \(v_1, v_2 \in K_{n-4}\) such that \(d_{E_4}(v_1) = d_{E_4}(v_2) = 3\). Then \(S_n\) is word-representable if and only if it contains none of \(T_1, T_2, T_3,T_5, T_6, T_8\) as induced subgraphs.

Proof. The necessary part of the proof follows directly from Remark 3.2.

For the sufficient part of the proof, let \(E_4 = \{a_0,a_1,b_0,b_1\}\). Throughout the proof, the indices of the vertices in Category-A and Category-B are taken modulo \(2\). Since \(S_n\) satisfies the conditions of Remark 2.12, no two vertices in \(S_n\) have the same neighborhood. Moreover, there are exactly two vertices \(v_1, v_2 \in K_{n-4}\) with \(d_{E_4}(v_1)=d_{E_4}(v_1)=3\). Hence, each vertex, except \(v_1, v_2\) in \(K_{n-4}\) corresponds to a distinct subset of \(E_4\) of size at most two. It follows that \(K_{n-4}\) can contain at most \(13\) vertices, namely \[\begin{aligned} &v_{\phi},\; v_{\{a_0\}},\; v_{\{a_1\}},\; v_{\{b_0\}},\; v_{\{b_1\}},\; v_{\{a_0,a_1\}},\; v_{\{a_0,b_0\}},\; v_{\{a_0,b_1\}},\\ &v_{\{a_1,b_0\}},\; v_{\{a_1,b_1\}},\; v_{\{b_0,b_1\}},\; v_{\{a_0,b_{0},b_{1}\}},\; v_{\{a_1,b_{0},b_{1}\}}. \end{aligned}\]

However, in a word-representable graph \(S_n\), there are at most four vertices of degree two with respect to \(E_4\). We regard the graph in Figure 9 as the basic underlying structure common to all \(S_n\) under this theorem, and any additional vertex introduced in the constructions below is treated as an extension vertex. In the following, we give seven observations that identify the graph extensions yielding \(T_1, T_2, T_3, T_5, T_6, T_8\) as induced subgraphs.

Obs. 1: If \(K\) contains \(v_{\{a_i,a_{i+1}\}}\) for some \(i\in \{0,1\}\), then addition of \(v_{\{b_{j}\}}\) or \(v_{\{b_{j+1}\}}\) or \(v_{\phi}\) yields an induced subgraph isomorphic to \(T_1\).

Obs. 2: If \(K\) contains \(\{ v_{\{a_i\}},\; v_{\{b_{j}\}},\; v_{\{b_{j+1}\}} \}\) for some \(i,j\in \{0,1\}\), then it has an induced subgraph isomorphic to \(T_2\).

Obs. 3: If \(K\) contains \(\{ v_{\{a_i,b_j\}},\; v_{\{a_{i},b_{j+1}\}} \}\) for some \(i,j\in \{0,1\}\), then it has an induced subgraph isomorphic to \(T_3\).

Obs. 4: If \(K\) contains four vertices that exhibit a cyclic neighborhood pattern on \(E_4\), then addition of \(v_{\phi}\) yields an induced subgraph isomorphic to \(T_5\).

Obs. 5: If \(K\) contains \(\{ v_{\{a_i\}},\; v_{\{a_{i+1}\}},\; v_{\{b_{j}\}} \}\) for some \(i,j\in \{0,1\}\), then it has an induced subgraph isomorphic to \(T_6\).

Obs. 6: If \(K\) contains \(\{ v_{\{a_i,b_{j}\}},\; v_{\{a_{i+1},b_{j}\}} \}\) for some \(i,j\in \{0,1\}\), then addition of \(v_{\{b_{j+1}\}}\) yields an induced subgraph isomorphic to \(T_8\).

Obs. 7: If \(K\) contains \(v_{\{a_i,b_{j}\}}\) for some \(i,j\in \{0,1\}\), then addition of \(v_{\{a_{i+1}\}}\) and \(v_{\{b_{j+1}\}}\) yields an induced subgraph isomorphic to \(T_2\).

As a consequence of Obs. 2 and 5, a word-representable extension cannot contain any three vertices from the set \(\{\,v_{\{a_i\}},\, v_{\{a_{i+1}\}},\, v_{\{b_j\}},\, v_{\{b_{j+1}\}}\,\}, \text{for } i,j \in \{0,1\},\) simultaneously. This observation will be used repeatedly throughout the proof to determine all possible word-representable extensions.

We first consider that \(S_n\) contains at least two \(2\)-degree extension vertices. Up to isomorphism, such pairs give rise to only six possible configurations (see Figure 13):

(i) they share a common neighbor in Category-A, and their remaining neighbors lie in Category-B (this graph contains \(T_3\) as an induced subgraph by Obs. 3, as shown in red in the first configuration of Figure 13);

(ii) they share a common neighbor in Category-A, and their remaining neighbors lie in both categories;

(iii) they share a common neighbor in Category-B, and their remaining neighbors lie in Category-A;

(iv) they share a common neighbor in Category-B, and their remaining neighbors lie in both categories;

(v) they do not share a common neighbor, and both vertices have neighbors in both categories; and

(vi) they do not share a common neighbor, where one vertex has neighbors only in Category-A and the other only in Category-B.

Since both Category-A and Category-B contain only two vertices, these six cases exhaust all possible configurations, thereby establishing the completeness of the case decomposition. As the first case contains \(T_3\) as an induced subgraph, it is excluded from further consideration. We therefore determine all possible word-representable extensions for the remaining five cases.

Case 1: \(K\) contains \(\{ v_{\{a_i,b_{j}\}},\; v_{\{a_{i},a_{i+1}\}}\}\) for some \(i,j \in \{0,1\}\).

By Obs. 1 neither \(v_{\{b_{j}\}}\) nor \(v_{\{b_{j+1}\}}\) nor \(v_{\phi}\) can be added. Also, by Obs. 7, \(\{ v_{\{a_{i+1}\}},v_{\{b_{j+1}\}} \}\) cannot be added.

Since the inclusion of \(v_{\{a_i,b_{j+1}\}}\) is excluded by Obs. 3, if an additional \(2\)-degree extension vertex is added, then it must be of the form \(v_{\{a_{i+1},b_j\}}\) or \(v_{\{a_{i+1},b_{j+1}\}}\) or \(v_{\{b_{j},b_{j+1}\}}\). Since the inclusion of \(\{v_{\{a_{i+1},b_{j}\}}\),\(v_{\{a_{i+1},b_{j+1}\}}\}\) is excluded by Obs. 3, if two additional \(2\)-degree extension vertices are added, then the possible pairs are \(\{v_{\{a_{i+1},b_j\}},v_{\{b_{j},b_{j+1}\}}\}\) or \(\{v_{\{a_{i+1},b_{j+1}\}},v_{\{b_{j},b_{j+1}\}}\}\). Below, we list all possible extensions that neither contain \(v_{\{b_{j}\}}\) nor \(v_{\{b_{j+1}\}}\) nor \(v_{\phi}\).

\(\hookrightarrow\) Word-representable extension containing \(\{v_{\{a_i,b_{j}\}}, v_{\{a_{i},a_{i+1}\}},v_{\{a_{i+1},b_{j}\}},v_{\{b_{j},b_{j+1}\}}\}\):

(i) \(K\): \(v_{\{a_i\}}>v_{\{a_{i},b_{j}\}}> v_{\{a_i,b_{j},b_{j+1}\}}>v_{\{b_{j},b_{j+1}\}}> v_{\{a_{i+1},b_{j},b_{j+1}\}}>v_{\{a_{i+1},b_{j}\}}> v_{\{a_{i+1}\}}>v_{\{a_i,a_{i+1}\}}\).

\(\hookrightarrow\) Word-representable extension containing \(\{v_{\{a_i,b_{j}\}}, v_{\{a_{i},a_{i+1}\}},v_{\{a_{i+1},b_{j+1}\}},v_{\{b_{j},b_{j+1}\}}\}\):

(ii) \(K\): \(v_{\{a_i\}}>v_{\{a_{i},b_{j}\}}> v_{\{a_i,b_{j},b_{j+1}\}}>v_{\{b_{j},b_{j+1}\}}> v_{\{a_{i+1},b_{j},b_{j+1}\}}>v_{\{a_{i+1},b_{j+1}\}}> v_{\{a_{i+1}\}}>v_{\{a_i,a_{i+1}\}}\).

Since the extensions listed in (i)-(ii) exhaust all possibilities under the condition of Obs. 1, it follows that, by deleting the two additional \(2\)-degree extension vertices and one of them, respectively, from each of these extensions, we obtain all possible word-representable extensions containing exactly two and three \(2\)-degree extension vertices in this case.

Case 2: \(K\) contains \(\{ v_{\{a_i,b_{j}\}},\; v_{\{a_{i+1},b_{j}\}}\}\) for some \(i,j \in \{0,1\}\).

By Obs. 6, \(v_{\{b_{j+1}\}}\) cannot be added.

Since by Obs. 3 neither \(v_{\{a_i,b_{j+1}\}}\) nor \(v_{\{a_{i+1},b_{j+1}\}}\) can be added, if an additional one \(2\)-degree extension vertex is added, then it must be of the form \(v_{\{b_{j},b_{j+1}\}}\) or \(v_{\{a_{i},a_{i+1}\}}\). If \(v_{\{a_{i},a_{i+1}\}}\) is present, then by Obs. 1 neither \(v_{\{b_{j}\}}\) nor \(v_{\{b_{j+1}\}}\) nor \(v_{\phi}\) can be added.

\(\hookrightarrow\) Word-representable extensions containing \(\{v_{\{a_i,b_{j}\}}, v_{\{a_{i+1},b_{j}\}},v_{\{b_{j},b_{j+1}\}}\}\):

(iii) \(K\): \(v_{\{a_i\}}>v_{\{a_i,b_{j}\}}> v_{\{a_i,b_{j},b_{j+1}\}}> v_{\{b_{j},b_{j+1}\}} >v_{\{a_{i+1},b_{j},b_{j+1}\}}>v_{\{a_{i+1},b_{j}\}}> v_{\{b_{j}\}}>v_{\phi}\).

(iv) \(K\): \(v_{\{b_j\}}>v_{\{a_i,b_{j}\}}> v_{\{a_i,b_{j},b_{j+1}\}}> v_{\{b_{j},b_{j+1}\}} >v_{\{a_{i+1},b_{j},b_{j+1}\}}>v_{\{a_{i+1},b_{j}\}}> v_{\{a_{i+1}\}}>v_{\phi}\).

(v) \(K\): \(v_{\{a_i\}}>v_{\{a_i,b_{j}\}}> v_{\{a_i,b_{j},b_{j+1}\}}> v_{\{b_{j},b_{j+1}\}} >v_{\{a_{i+1},b_{j},b_{j+1}\}}>v_{\{a_{i+1},b_{j}\}}> v_{\{a_{i+1}\}}>v_{\phi}\).

\(\hookrightarrow\) Word-representable extension containing \(\{v_{\{a_i,b_{j}\}},v_{\{a_{i+1},b_{j}\}},v_{\{a_{i},a_{i+1}\}}\}\):

(vi) \(K\): \(v_{\{a_i\}}>v_{\{a_{i},b_{j}\}}> v_{\{a_i,b_{j},b_{j+1}\}}> v_{\{a_{i+1},b_{j},b_{j+1}\}}>v_{\{a_{i+1},b_{j}\}}> v_{\{a_{i+1}\}}>v_{\{a_i,a_{i+1}\}}\).

Note that the extensions listed in (iii)-(v) realize all possible combinations of two \(1\)-degree extension vertices together with \(v_{\phi}\), subject to the exclusion of \(v_{\{b_{j+1}\}}\) by Obs. 6. Consequently, by deleting the additional \(2\)-degree extension vertex from each of these extensions, we obtain all possible word-representable extensions containing exactly two \(2\)-degree extension vertices in this case.

Since by Obs. 3 neither \(v_{\{a_i,b_{j+1}\}}\) nor \(v_{\{a_{i+1},b_{j+1}\}}\) can be added, if two additional \(2\)-degree extension vertices are added, then the possible pair is \(\{v_{\{a_{i},a_{i+1}\}},v_{\{b_{j},b_{j+1}\}}\}\). We use Obs. 1 to obtain all word-representable extensions.

\(\hookrightarrow\) Word-representable extension containing \(\{v_{\{a_i,b_{j}\}}, v_{\{a_{i+1},b_{j}\}},v_{\{a_{i},a_{i+1}\}},v_{\{b_{j},b_{j+1}\}}\}\):

(vii) \(K\): \(v_{\{a_i\}}> v_{\{a_{i},b_{j}\}}> v_{\{a_i,b_{j},b_{j+1}\}}>v_{\{b_{j},b_{j+1}\}}> v_{\{a_{i+1},b_{j},b_{j+1}\}}>v_{\{a_{i+1},b_{j}\}}> v_{\{a_{i+1}\}}>v_{\{a_i,a_{i+1}\}}\).

Case 3: \(K\) contains \(\{ v_{\{a_i,b_{j}\}},\; v_{\{b_{j},b_{j+1}\}}\}\) for some \(i,j \in \{0,1\}\).

By Obs. 7, \(\{ v_{\{a_{i+1}\}} , v_{\{b_{j+1}\}} \}\) cannot be added.

Since the inclusion of \(v_{\{a_i,b_{j+1}\}}\) is excluded by Obs. 3, if an additional \(2\)-degree extension vertex is added, then it must be of the form \(v_{\{a_{i+1},b_j\}}\) or \(v_{\{a_{i+1},b_{j+1}\}}\) or \(v_{\{a_{i},a_{i+1}\}}\). If \(v_{\{a_{i+1},b_{j}\}}\) is present, then by Obs. 6, \(v_{\{b_{j+1}\}}\) cannot be added. If \(v_{\{a_{i+1},b_{j+1}\}}\) is present, then by Obs. 7, \(\{v_{\{a_{i}\}},v_{\{b_{j}\}}\}\) cannot be added. If \(v_{\{a_{i},a_{i+1}\}}\) is present, then by Obs. 1 neither \(v_{\{b_{j}\}}\) nor \(v_{\{b_{j+1}\}}\) nor \(v_{\phi}\) can be added.

\(\hookrightarrow\) Word-representable extensions containing \(\{v_{\{a_i,b_{j}\}},\; v_{\{b_{j},b_{j+1}\}},v_{\{a_{i+1},b_j\}}\}\):

(viii) \(K\): \(v_{\{a_i\}}> v_{\{a_{i},b_{j}\}}> v_{\{a_i,b_{j},b_{j+1}\}}>v_{\{b_{j},b_{j+1}\}}> v_{\{a_{i+1},b_{j},b_{j+1}\}}>v_{\{a_{i+1},b_{j}\}}> v_{\{a_{i+1}\}}>v_{\phi}\).

(ix) \(K\): \(v_{\{a_i\}}> v_{\{a_{i},b_{j}\}}> v_{\{a_i,b_{j},b_{j+1}\}}>v_{\{b_{j},b_{j+1}\}}> v_{\{a_{i+1},b_{j},b_{j+1}\}}>v_{\{a_{i+1},b_{j}\}}> v_{\{b_{j}\}}>v_{\phi}\).

(x) \(K\): \(v_{\{b_j\}}> v_{\{a_{i},b_{j}\}}> v_{\{a_i,b_{j},b_{j+1}\}}>v_{\{b_{j},b_{j+1}\}}> v_{\{a_{i+1},b_{j},b_{j+1}\}}>v_{\{a_{i+1},b_{j}\}}> v_{\{a_{i+1}\}}>v_{\phi}\).

\(\hookrightarrow\) Word-representable extensions containing \(\{v_{\{a_i,b_{j}\}},\; v_{\{b_{j},b_{j+1}\}}v_{\{a_{i+1},b_{j+1}\}}\}\):

(xi) \(K\): \(v_{\{a_i\}}> v_{\{a_{i},b_{j}\}}> v_{\{a_i,b_{j},b_{j+1}\}}>v_{\{b_{j},b_{j+1}\}}> v_{\{a_{i+1},b_{j},b_{j+1}\}}>v_{\{a_{i+1},b_{j+1}\}}> v_{\{b_{j+1}\}}>v_{\phi}\).

(xii) \(K\): \(v_{\{b_j\}}> v_{\{a_{i},b_{j}\}}> v_{\{a_i,b_{j},b_{j+1}\}}>v_{\{b_{j},b_{j+1}\}}> v_{\{a_{i+1},b_{j},b_{j+1}\}}>v_{\{a_{i+1},b_{j+1}\}}> v_{\{b_{j+1}\}}>v_{\phi}\).

(xiii) \(K\): \(v_{\{a_i\}}> v_{\{a_{i},b_{j}\}}> v_{\{a_i,b_{j},b_{j+1}\}}>v_{\{b_{j},b_{j+1}\}}> v_{\{a_{i+1},b_{j},b_{j+1}\}}>v_{\{a_{i+1},b_{j+1}\}}> v_{\{a_{i+1}\}}>v_{\phi}\).

(xiv) \(K\): \(v_{\{b_j\}}> v_{\{a_{i},b_{j}\}}> v_{\{a_i,b_{j},b_{j+1}\}}>v_{\{b_{j},b_{j+1}\}}> v_{\{a_{i+1},b_{j},b_{j+1}\}}>v_{\{a_{i+1},b_{j+1}\}}> v_{\{a_{i+1}\}}>v_{\phi}\).

\(\hookrightarrow\) Word-representable extension containing \(\{v_{\{a_i,b_{j}\}},v_{\{b_{j},b_{j+1}\}},v_{\{a_{i},a_{i+1}\}}\}\):

(xv) \(K\): \(v_{\{a_i\}}> v_{\{a_{i},b_{j}\}}> v_{\{a_i,b_{j},b_{j+1}\}}>v_{\{b_{j},b_{j+1}\}}> v_{\{a_{i+1},b_{j},b_{j+1}\}}> v_{\{a_{i+1}\}}>v_{\{a_i,a_{i+1}\}}\).

Note that the extensions listed in (viii)-(xii) realize all possible combinations of two \(1\)-degree extension vertices together with \(v_{\phi}\), subject to the exclusion of \(\{v_{\{a_{i+1}\}}, v_{\{b_{j+1}\}}\}\) by Obs. 7. Consequently, by deleting the additional \(2\)-degree extension vertex from each of these extensions, we obtain all possible word-representable extensions containing exactly two \(2\)-degree extension vertices in this case.

Since by Obs. 3 neither \(v_{\{a_i,b_{j+1}\}}\) nor \(\{v_{\{a_{i+1},b_{j}\}}\),\(v_{\{a_{i+1},b_{j+1}\}}\}\) can be added , if two additional \(2\)-degree extension vertices are added, then the possible pairs are \(\{v_{\{a_{i+1},b_j\}},v_{\{a_{i},a_{i+1}\}}\}\) or \(\{v_{\{a_{i+1},b_{j+1}\}},v_{\{a_{i},a_{i+1}\}}\}\). We use Obs. 1 to obtain all word-representable extensions.

\(\hookrightarrow\) Word-representable extension containing \(\{v_{\{a_i,b_{j}\}},v_{\{b_{j},b_{j+1}\}},v_{\{a_{i+1},b_j\}},v_{\{a_{i},a_{i+1}\}}\}\):

(xvi) \(K\): \(v_{\{a_i\}}> v_{\{a_{i},b_{j}\}}> v_{\{a_i,b_{j},b_{j+1}\}}>v_{\{b_{j},b_{j+1}\}}> v_{\{a_{i+1},b_{j},b_{j+1}\}}>v_{\{a_{i+1},b_{j}\}}> v_{\{a_{i+1}\}}>v_{\{a_i,a_{i+1}\}}\).

\(\hookrightarrow\) Word-representable extension containing \(\{v_{\{a_i,b_{j}\}}, v_{\{b_{j},b_{j+1}\}},v_{\{a_{i+1},b_{j+1}\}},v_{\{a_{i},a_{i+1}\}}\}\):

(xvii) \(K\): \(v_{\{a_i\}}> v_{\{a_{i},b_{j}\}}> v_{\{a_i,b_{j},b_{j+1}\}}>v_{\{b_{j},b_{j+1}\}}> v_{\{a_{i+1},b_{j},b_{j+1}\}}>v_{\{a_{i+1},b_{j+1}\}}> v_{\{a_{i+1}\}}>v_{\{a_i,a_{i+1}\}}\).

Case 4: \(K\) contains \(\{ v_{\{a_i,b_{j}\}},\; v_{\{a_{i+1},b_{j+1}\}}\}\) for some \(i,j \in \{0,1\}\).

By Obs. 7, neither \(\{ v_{\{a_{i+1}\}},v_{\{b_{j+1}\}} \}\) nor \(\{ v_{\{a_{i}\}},v_{\{b_{j}\}} \}\) can be added.

Since by Obs. 3, neither \(v_{\{a_i,b_{j+1}\}}\) nor \(v_{\{a_{i+1},b_{j}\}}\) can be added, if an additional \(2\)-degree extension vertex is added, then it must be of the form \(v_{\{b_j,b_{j+1}\}}\), or \(v_{\{a_{i},a_{i+1}\}}\). If \(v_{\{a_{i},a_{i+1}\}}\) is present, then by Obs. 1 neither \(v_{\{b_{j}\}}\) nor \(v_{\{b_{j+1}\}}\) nor \(v_{\phi}\) can be added.

\(\hookrightarrow\) Word-representable extensions containing \(\{ v_{\{a_i,b_{j}\}},v_{\{a_{i+1},b_{j+1}\}},v_{\{b_j,b_{j+1}\}}\}\):

(xviii) \(K\): \(v_{\{a_i\}}>v_{\{a_i,b_{j}\}}> v_{\{a_i,b_{j},b_{j+1}\}}> v_{\{b_{j},b_{j+1}\}} >v_{\{a_{i+1},b_{j},b_{j+1}\}}>v_{\{a_{i+1},b_{j+1}\}}> v_{\{b_{j+1}\}}>v_{\phi}\).

(xix) \(K\): \(v_{\{b_j\}}>v_{\{a_i,b_{j}\}}> v_{\{a_i,b_{j},b_{j+1}\}}> v_{\{b_{j},b_{j+1}\}} >v_{\{a_{i+1},b_{j},b_{j+1}\}}>v_{\{a_{i+1},b_{j+1}\}}> v_{\{a_{i+1}\}}>v_{\phi}\).

(xx) \(K\): \(v_{\{a_i\}}>v_{\{a_i,b_{j}\}}> v_{\{a_i,b_{j},b_{j+1}\}}> v_{\{b_{j},b_{j+1}\}} >v_{\{a_{i+1},b_{j},b_{j+1}\}}>v_{\{a_{i+1},b_{j+1}\}}> v_{\{a_{i+1}\}}>v_{\phi}\).

(xxi) \(K\): \(v_{\{b_j\}}>v_{\{a_i,b_{j}\}}> v_{\{a_i,b_{j},b_{j+1}\}}> v_{\{b_{j},b_{j+1}\}} >v_{\{a_{i+1},b_{j},b_{j+1}\}}>v_{\{a_{i+1},b_{j+1}\}}> v_{\{b_{j+1}\}}>v_{\phi}\).

\(\hookrightarrow\) Word-representable extension containing \(\{ v_{\{a_i,b_{j}\}},v_{\{a_{i+1},b_{j+1}\}} ,v_{\{a_{i},a_{i+1}\}}\}\):

(xxii) \(K\): \(v_{\{a_i\}}>v_{\{a_i,b_{j}\}}> v_{\{a_i,b_{j},b_{j+1}\}} >v_{\{a_{i+1},b_{j},b_{j+1}\}}>v_{\{a_{i+1},b_{j+1}\}}> v_{\{a_{i+1}\}}> v_{\{a_{i},a_{i+1}\}}\).

Note that the extensions listed in (xviii)-(xxi) realize all possible combinations of two \(1\)-degree extension vertices together with \(v_{\phi}\), subject to the exclusion of \(\{v_{\{a_{i+1}\}}, v_{\{b_{j+1}\}}\}\) and \(\{v_{\{a_i\}}, v_{\{b_{j}\}}\}\) by Obs. 7. Consequently, by deleting the additional \(2\)-degree extension vertex from each of these extensions, we obtain all possible word-representable extensions containing exactly two \(2\)-degree extension vertices in this case.

Since by Obs. 3, neither \(v_{\{a_i,b_{j+1}\}}\) nor \(v_{\{a_{i+1},b_{j}\}}\) can be added, if two additional 2-degree extension vertices are added, then the only possible pair is \(\{v_{\{a_{i},a_{i+1}\}},v_{\{b_{j},b_{j+1}\}}\}\). We use Obs. 1 to obtain all possible word-representable extensions.

\(\hookrightarrow\) Word-representable extension containing \(\{ v_{\{a_i,b_{j}\}}, v_{\{a_{i},a_{i+1}\}} ,v_{\{a_{i},a_{i+1}\}},v_{\{b_{j},b_{j+1}\}}\}\):

(xxiii) \(K\): \(v_{\{a_i\}}> v_{\{a_{i},b_{j}\}}> v_{\{a_i,b_{j},b_{j+1}\}}>v_{\{b_{j},b_{j+1}\}}> v_{\{a_{i+1},b_{j},b_{j+1}\}}>v_{\{a_{i+1},b_{j+1}\}}> v_{\{a_{i+1}\}}>v_{\{a_i,a_{i+1}\}}\).

Case 5: \(K\) contains \(\{ v_{\{a_i,a_{i+1}\}},\; v_{\{b_{j},b_{j+1}\}}\}\) for some \(i,j \in \{0,1\}\).

By Obs. 1 neither \(v_{\{b_{j}\}}\) nor \(v_{\{b_{j+1}\}}\) nor \(v_{\phi}\) can be added.

If an additional \(2\)-degree extension vertex is added, then it must be of the form \(v_{\{a_i,b_{j}\}}\) or \(v_{\{a_{i+1},b_{j+1}\}}\) or \(v_{\{a_{i+1},b_{j}\}}\) or \(v_{\{a_{i},b_{j+1}\}}\). Since, by Obs. 3 neither \(\{v_{\{a_{i},b_{j}\}}\),\(v_{\{a_{i},b_{j+1}\}}\}\) nor \(\{v_{\{a_{i+1},b_{j}\}}\),\(v_{\{a_{i+1},b_{j+1}\}}\}\) can be added, if two additional \(2\)-degree extension vertices are added, then the possible pairs are \(\{v_{\{a_{i},b_j\}},v_{\{a_{i+1},b_{j}\}}\}\) or \(\{v_{\{a_{i},b_j\}},v_{\{a_{i+1},b_{j+1}\}}\}\) or \(\{v_{\{a_{i},b_{j+1}\}},\\v_{\{a_{i+1},b_{j}\}}\}\) or \(\{v_{\{a_{i},b_{j+1}\}},v_{\{a_{i+1},b_{j+1}\}}\}\). Below, we list all possible extensions that neither contain \(v_{\{b_{j}\}}\) nor \(v_{\{b_{j+1}\}}\) nor \(v_{\phi}\).

\(\hookrightarrow\) Word-representable extension containing \(\{v_{\{a_i,a_{i+1}\}}, v_{\{b_{j},b_{j+1}\}},v_{\{a_{i},b_j\}},v_{\{a_{i+1},b_{j}\}}\}\):

(xxiv) \(K\): \(v_{\{a_i\}}> v_{\{a_{i},b_{j}\}}> v_{\{a_i,b_{j},b_{j+1}\}}>v_{\{b_{j},b_{j+1}\}}> v_{\{a_{i+1},b_{j},b_{j+1}\}}>v_{\{a_{i+1},b_{j}\}}> v_{\{a_{i+1}\}}>v_{\{a_i,a_{i+1}\}}\).

\(\hookrightarrow\) Word-representable extension containing \(\{v_{\{a_i,a_{i+1}\}}, v_{\{b_{j},b_{j+1}\}},v_{\{a_{i},b_j\}},v_{\{a_{i+1},b_{j+1}\}}\}\):

(xxv) \(K\): \(v_{\{a_i\}}> v_{\{a_{i},b_{j}\}}> v_{\{a_i,b_{j},b_{j+1}\}}>v_{\{b_{j},b_{j+1}\}}> v_{\{a_{i+1},b_{j},b_{j+1}\}}>v_{\{a_{i+1},b_{j+1}\}}> v_{\{a_{i+1}\}}>v_{\{a_i,a_{i+1}\}}\).

\(\hookrightarrow\) Word-representable extension containing \(\{v_{\{a_i,a_{i+1}\}},v_{\{b_{j},b_{j+1}\}},v_{\{a_{i},b_{j+1}\}},v_{\{a_{i+1},b_{j}\}}\}\):

(xxvi) \(K\): \(v_{\{a_i\}}> v_{\{a_{i},b_{j+1}\}}> v_{\{a_i,b_{j},b_{j+1}\}}>v_{\{b_{j},b_{j+1}\}}> v_{\{a_{i+1},b_{j},b_{j+1}\}}>v_{\{a_{i+1},b_{j}\}}> v_{\{a_{i+1}\}}>v_{\{a_i,a_{i+1}\}}\).

\(\hookrightarrow\) Word-representable extension containing \(\{v_{\{a_i,a_{i+1}\}}, v_{\{b_{j},b_{j+1}\}},v_{\{a_{i},b_{j+1}\}},v_{\{a_{i+1},b_{j+1}\}}\}\):

(xxvii) \(K\): \(v_{\{a_i\}}> v_{\{a_{i},b_{j+1}\}}> v_{\{a_i,b_{j},b_{j+1}\}}>v_{\{b_{j},b_{j+1}\}}> v_{\{a_{i+1},b_{j},b_{j+1}\}}>v_{\{a_{i+1},b_{j+1}\}}> v_{\{a_{i+1}\}}>v_{\{a_i,a_{i+1}\}}\).

Since the extensions listed in (xxiv)-(xxvii) exhaust all possibilities under the condition of Obs. 1, it follows that, by deleting the two additional \(2\)-degree extension vertices and one of them, respectively, from each of these extensions, we obtain all possible word-representable extensions containing exactly two and three \(2\)-degree extension vertices in this case.

We observe that if \(S_n\) contains at most one \(2\)-degree extension vertex, then any such vertex has, up to isomorphism, only three possible forms: (i) \(v_{\{a_i,a_{i+1}\}}\) for some \(i\in\{0,1\}\), that is, both of its neighbors in \(E_4\) belong to Category-A; or (ii) \(v_{\{b_j,b_{j+1}\}}\) for some \(j\in\{0,1\}\), that is, both of its neighbors in \(E_4\) belong to Category-B; or (iii) \(v_{\{a_i,b_j\}}\) for some \(i,j\in\{0,1\}\), that is, it has neighbors in both categories.

If \(v_{\{a_i,a_{i+1}\}}\) is present, then by Obs. 1, neither \(v_{\{b_{j}\}}\) nor \(v_{\{b_{j+1}\}}\) nor \(v_{\phi}\) can be added. If \(v_{\{a_i,b_j\}}\) is present, then by Obs. 7, \(\{ v_{\{a_{i+1}\}} , v_{\{b_{j+1}\}}\}\) cannot be added.

Note that the extension (xv) realizes all possible combinations of two \(1\)-degree extension vertices containing neither \(v_{\{b_j\}}\) nor \(v_{\{b_{j+1}\}}\) nor \(v_{\phi}\), as required by Obs. 1. Consequently, by deleting all \(2\)-degree extension vertices other than \(v_{\{a_i,a_{i+1}\}}\), we obtain word-representable extensions containing at most one \(2\)-degree extension vertex of the form \(v_{\{a_i,a_{i+1}\}}\).

Similarly, the extensions listed in (viii)-(xii) realize all possible combinations of two \(1\)-degree extension vertices together with \(v_{\phi}\), except for \(\{v_{\{a_{i+1}\}}, v_{\{b_{j+1}\}}\}\), which is excluded by Obs. 7. Hence, deleting all \(2\)-degree extension vertices other than \(v_{\{a_i,b_j\}}\) yields all word-representable extensions containing at most one \(2\)-degree extension vertex of the form \(v_{\{a_i,b_j\}}\).

Likewise, deleting all \(2\)-degree extension vertices other than \(v_{\{b_j,b_{j+1}\}}\) from (viii)-(xii) gives all word-representable extensions containing at most one \(2\)-degree extension vertex of the form \(v_{\{b_j,b_{j+1}\}}\), except for the following additional case: \[K: v_{\{b_{j+1}\}}>v_{\{a_i,b_j,b_{j+1}\}}> v_{\{b_j,b_{j+1}\}}> v_{\{a_{i+1},b_j,b_{j+1}\}}> v_{\{a_{i+1}\}}>v_{\phi}.\] This completes the proof. \(\square\)

Remark 3.14. Since Theorems 3.11–3.13 are stated under the conditions of Remark 3.8, it follows that in each of these theorems there are at most four vertices in the clique whose degree with respect to the independent set is two. If this condition is removed, then by Lemma 3.7, the graph \(T_7\) must also be included in the list of forbidden induced subgraphs in each theorem. We will make use of this observation in the proof of Theorem 3.3.

Proof of Theorem 3.3. (\(\Rightarrow\)) Let \(S_n = (E_4, K_{n-4})\) contain at least one of \(T_1, T_2, \ldots, T_8\) or \(D_1\) as an induced subgraph. By Remark 3.2, each of \(T_1, T_2, \ldots, T_8 ,D_1\) is non-word-representable. Since word-representability is closed under taking induced subgraphs, it follows that \(S_n\) is non-word-representable. Therefore, if \(S_n\) is word-representable, then it contains none of \(T_1, T_2, \ldots, T_8, D_1\) as induced subgraphs.

Table 1. Case-wise classification of split graphs \(S_n=(E_{n-4},K_{n-4})\) based on degree conditions in the clique, together with the corresponding forbidden induced subgraphs

Degree conditions on the vertices of \(K_{n-4}\)	Forbidden induced subgraphs
\(\exists\) a vertex \(v \in K_{n-4}\) such that \(d_{E_4}(v)=4\)	\(T_2,T_3,T_4\) (Theorem 3.5)
\(\nexists\) a vertex \(v \in K_{n-4}\) such that \(d_{E_4}(v)=4\) and \(\exists\) at least three vertices \(v_1,v_2,v_3\in K_{n-4}\) such that \(d_{E_4}(v_1)=d_{E_4}(v_2)=d_{E_4}(v_3)=3\)	Such a graph always contains \(T_1\) by Lemma 3.6
\(\nexists\) a vertex \(v \in K_{n-4}\) such that \(d_{E_4}(v)=4\) and \(\exists\) exactly two vertices \(v_1,v_2\in K_{n-4}\) such that \(d_{E_4}(v_1)=d_{E_4}(v_2)=3\)	\(T_1,T_2,T_3,T_5,T_6,T_7,T_8\) (Theorem 3.13, Remark 3.14)
\(\nexists\) a vertex \(v \in K_{n-4}\) such that \(d_{E_4}(v)=4\) and \(\exists\) exactly one vertex \(v_1\in K_{n-4}\) such that \(d_{E_4}(v_1)=3\)	\(T_1,T_2,T_3,T_5,T_7\) (Theorem 3.12 and Remark 3.14)
\(\nexists\) a vertex \(v \in K_{n-4}\) such that \(d_{E_4}(v)=4\) and \(\nexists\) a vertex \(v_1\in K_{n-4}\) such that \(d_{E_4}(v_1)=3\)	\(T_1,T_5,T_7,D_1\) (Theorem 3.11 and Remark 3.14)

(\(\Leftarrow\)) Conversely, let \(S_n\) be a split graph that contains none of \(T_1, T_2, \ldots, T_8, D_1\) as induced subgraphs. We show that \(S_n\) is word-representable by establishing that this collection forms a complete list of forbidden induced subgraphs.

By Remark 2.12, we may assume that no two vertices in \(S_n\) have the same neighborhood. Moreover, since \(|E|=4\), we have \(d_E(v)\le 4\) for every vertex \(v\in K_{n-4}\). Using these observations, we decompose the problem space into five cases according to the degree pattern of vertices in \(K_{n-4}\): either there exists a vertex of degree \(4\) with respect to \(E_4\), or no such vertex exists, in which case the number of vertices of degree \(3\) with respect to \(E_4\) is \(0,1,2,\) or at least \(3\). These five possibilities are mutually exclusive and exhaustive. We characterize each case separately in terms of forbidden induced subgraphs (see Table 1). Consequently, the union of the forbidden induced subgraphs obtained from all five cases yields the complete list for the entire class. This completes the proof. \(\square\)

4. Concluding Remarks

In this work, we have provided a characterization of word-representable graphs for a specific subclass of split graphs with \(|E| = 4\). Toward the development of a complete list of minimal forbidden induced subgraphs for word-representable split graphs, we draw attention to the work of Bonomo-Braberman et al.[1], where a forbidden induced subgraph characterization of circle graphs within the class of split graphs is established. Notably, except \(T_6\) and \(T_7\), all graphs in our list (i.e, \(T_1, T_2, T_3, T_4, T_5, T_8, D_1\)) also appear in the list of forbidden induced subgraphs presented in [1]. In what follows, we explicitly describe the correspondence between the graphs in our list and the graphs in [1].

• The graphs \(T_1\) and \(T_5\) belong to the infinite family of odd \(k\)-sun with center, corresponding to \(k=4\) and \(k=5\), respectively.

• The graphs \(T_2 \cong M_{III}(3)\), \(T_3 \cong \text{tent} \mathbin{\vee} K_1\), \(T_8 \cong M_V\), and \(D_1 \cong M_{IV}\).

• The graph \(T_4\) belongs to the infinite family \(\{M_{II}(k) : k(\ge 4) \text{ even} \}\), corresponding to \(k=4\).

As a natural next step, it would be worthwhile to investigate whether the remaining graphs \(T_6\) and \(T_7\) admit generalizations to infinite families as {\(M_{II}(k) : k(\ge 4) \text{ even}\}\), or whether they remain isolated obstructions, similar to \(T_3\), \(T_8\) and \(D_1\).

Furthermore, the identification of minimal forbidden induced subgraphs in this work, together with existing results in [1, 2, 7], reveals an interesting numerical pattern. For instance, when \(|E|=4\) and \(|K|=5\), the number of minimal forbidden induced subgraphs is \(9\) in both cases. In contrast, for \(|E|=3\) and \(|K|=4\), the counts are \(3\) and \(4\), respectively.

Although these observations are independent of the results proved in this work, they motivate the following conjecture.

Conjecture 4.1. The absolute difference between the number of minimal forbidden induced subgraphs corresponding to \(|E|\) and \(|K|=|E|+1\) is at most \(1\).

This conjecture also suggests a possible line of investigation. For a fixed independent set size \(|E|=t\), one may consider an inductive approach, assuming that the characterization is known for smaller values, such as \(|E|=t-1\) and \(|K|=t\). The structural decomposition developed in this work suggests that the problem may be reducible to a bounded family of configurations. For instance, analogues of Theorem 3.5 could address graphs containing a universal vertex, while extensions of Remark 3.8 suggest any such graph can contain at most two vertices whose degree with respect to \(E\) is \(t-1\), and at most four vertices whose degree with respect to \(E\) is \(t-2\).

We included these observations to indicate potential directions for future work.