Characterization of Circular-arc Graphs: III. Chordal Graphs
Yixin Cao Tomasz Krawczyk

Reply to Comment on “A slightly oblate dark matter halo revealed by a retrograde precessing Galactic disk warp"
    Haibo Yuan
    September 9, 2024
===============================================================================================================

§ ABSTRACT 
  We identify all minimal chordal graphs that are not circular-arc graphs, thereby resolving one of “the main open problems” concerning the structures of circular-arc graphs as posed by Durán, Grippo, and Safe in 2011.
  The problem had been attempted even earlier, and previous efforts have yielded partial results, particularly for claw-free graphs and graphs with an independence number of at most four.
  The answers turn out to have very simple structures: all the nontrivial ones belong to a single family.
  Our findings are based on a structural study of McConnell's flipping, which transforms circular-arc graphs into interval graphs with certain representation patterns.




§ INTRODUCTION


A graph is a circular-arc graph if its vertices can be assigned to arcs on a circle such that two vertices are adjacent if and only if their corresponding arcs intersect.  Such a set of arcs is called a circular-arc model for this graph (Figure <ref>).
If we replace the circle with the real line and arcs with intervals, we end with interval graphs.
All interval graphs are circular-arc graphs.
Both graph classes are by definition hereditary, i.e., closed under taking induced subgraphs.



While both classes have been intensively studied, there is a huge gap between our understanding of them.
One fundamental combinatorial problem on a hereditary graph class is its characterization by forbidden induced subgraphs, i.e., minimal graphs that are not in the class.
For example, the forbidden induced subgraphs of interval graphs are holes (induced cycles of length at least four) and those in Figure <ref> <cit.>.  The same problem on circular-arc graphs, however, has been open for sixty years <cit.>.




  
  A graph is an interval graph if and only if it does not contain any hole or any graph in Figure <ref> as an induced subgraph.


It is already very complicated to characterize chordal circular-arc graphs by forbidden induced subgraphs.
Chordal graphs, graphs in which all induced cycles are triangles, are another superclass of interval graphs.
Thus, all interval graphs are chordal circular-arc graphs.
We rely on the reader to check that the long claw (Figure <ref>) and † graphs (Figure <ref>) on seven or more vertices are not circular-arc graphs.
Thus, they are chordal forbidden induced subgraphs of circular-arc graphs.  Other forbidden induced subgraphs must contain a whipping top, a net (the † graph on six vertices), or a  graph (Figure <ref>), which are all circular-arc graphs.  However, except for adding an isolated vertex, there is no obvious way to augment them to derive forbidden induced subgraphs, not to mention enumerating forbidden induced subgraphs exhaustively.
For example, let us consider chordal forbidden induced subgraph of circular-arc graphs on ten or fewer vertices.
There are 20 such graphs.  Nine of them can be obtained in the aforementioned way,
while only four of the remaining 11 have been identified in literature <cit.>.  See the appendix for the list.

Bonomo et al. <cit.> characterized chordal circular-arc graphs that are claw-free.
There are only four of them.  Through generalizing Lekkerkerker and Boland's <cit.> structural characterization of interval graphs, Francis et al. <cit.> defined a forbidden structure of circular-arc graphs.
This observation enabled them to characterize chordal circular-arc graphs with independence number at most four.
As we will see, most chordal forbidden induced subgraphs of circular-arc graphs contain an induced claw, and their independence numbers can be arbitrarily large.
These unsuccessful attempts motivated Durán et al. <cit.> to list the forbidden induced subgraph characterization for circular-arc graphs within the class of chordal graphs one of “the main open problems.”
Bang-Jensen and Hell <cit.> characterized proper circular-arc graphs (i.e., graphs admitting circular-arc models in which no arc properly contains another) that are chordal.

In a previous paper <cit.> of this series, we derived a full characterization of minimal split graphs that are not circular-arc graphs.  Recall that a graph is a split graph if its vertex set can be partitioned into a clique and an independent set, and hence all split graphs are chordal.





  
The ⊗ graphs.
The main discovery of the present paper is the family of ⊗ graphs.
For k ≥ 2, the k-sun, denoted as S_k, is the graph obtained from a cycle of length 2 k by adding all edges among the even-numbered vertices to make them a clique.
The complement of S_k, denoted as S_k,
is a split graph with a unique split partition, and each vertex has precisely two non-neighbors in the other part.
See Figure <ref> for the smallest examples of S_k.
Note that S_4 and  S_4 are isomorphic, while S_3 and S_3 are the net and the sun, respectively.




For k ≥ 1, we define the gadget D_k as a subgraph of S_k+1 obtained by removing one vertex of degree 2k - 1 (a solid node in Figure <ref>).
An example is illustrated in Figure <ref>, where the removed vertex was adjacent to w_1, …, w_k - 1.
The gadget D_k consists of 2 k + 1 vertices.  
The vertex set {v_1, v_2, …, v_k} is a clique, hence called the clique vertices of this gadget.
The remaining vertices, {w_0, w_1, …, w_k}, is an independent set, and for i = 0, 1, …, k,

    N(w_i) = {v_1, v_2, …, v_k}∖{v_i, v_i+1}.

The vertices w_0 and w_k are called the ends of this gadget; their degrees in the gadget are k - 1 (while the degrees of other vertices are k - 2 and 2 k - 2; note that k - 1 = 2 k - 2 only when k = 1).



We are now ready to describe the main family of chordal forbidden induced subgraphs of circular-arc graphs.  Let p be a positive integer and ⟨ a_0, a_1, …, a_2 p - 1⟩ a sequence of 2 p positive integers.  For i = 0, …, p-1, we introduce a gadget D_a_2 i and a path P_a_2i + 1.
For each gadget and each path, we arbitrarily assign the ends as the left end and the right end.  (Note that the two ends are identical for a trivial path.)
We put the gadgets and paths in order circularly, and connect the right end of one gadget/path with the left end of next path/gadget.
We also introduce a special vertex c, and this concludes the vertex set.
For each gadget, we add edges between its clique vertices and all other vertices not in this gadget.
The resulting graph is denoted as ⊗(a_0, a_1, …, a_2 p - 1).
See Figure <ref> for an illustration and below are two simple examples. 


  * Graph ⊗(1, a) with a ≥ 2 is the † graph of order a + 4 (Figure <ref>).
Here c is the degree-one vertex at the top, the gadget D_1 comprises the other two degree-one vertices and the vertex of degree a+1, while the path comprises the remaining vertices (at the bottom).

  * Graph ⊗(2, a) is the  graph of order a + 5 (Figure <ref>) augmented with an isolated vertex.  Here  
c is the degree-two vertex at the top, the gadget D_2 comprises the other two degree-two vertices and the two vertices of degree a+3, while the path comprises the remaining vertices (at the bottom).

Illustrations of ⊗(a, b) and ⊗(1, a, 1, b) for small a and b can be found in the appendix.
Note that the order of the graph ⊗(a_0, a_1, …, a_2 p - 1) is

    1 + ∑^p-1_i=0 (2 a_2 i + 1 + a_2 i + 1) = p + 1 + ∑^2 p-1_i=0 a_i + ∑^p-1_i=0 a_2 i.

Graphs ⊗(1, 1) and ⊗(1, 2) are circular-arc graphs.  They are the only circular-arc graphs that arise from this construction.


Let p be a positive integer, and let G be the graph ⊗(a_0, a_1, …, a_2 p - 1), where (a_0, a_1, …, a_2 p - 1) is a sequence of positive integers different from (1, 1) and (1, 2).
  
  
  * G is a chordal graph;
  
  * G is not a circular-arc graph; and
  
  * for any vertex x∈ V(G), the graph G - x is a Helly circular-arc graph.
  


All ⊗(a_0, a_1, …, a_2 p - 1) graphs that are not ⊗(1, 1) or ⊗(1, 2) are called ⊗ graphs.
It is worth noting that the ⊗ graphs defined by two different sequences might be the same.  For example, the following sequences define the same ⊗ graph:
(1, 2, 3, 4), (3, 4, 1, 2), (3, 2, 1, 4), and (1, 4, 3, 2).





  
Our results.
The algorithm of McConnell <cit.> recognizes circular-arc graphs by transforming them into interval graphs.
Let G be a circular-arc graph and 𝒜 a fixed arc model of G.
If we flip all arcs—replace arc [, ] with arc [, ]—containing a certain point in 𝒜, we end with an interval model ℐ.
In Figure <ref>b, for example, if we flip arcs 2, 4, and 6, all containing the clockwise endpoint of the arc 4, we end with a † graph of six vertices.
A crucial observation of McConnell is that the resulting interval graph is decided by the set of vertices whose arcs are flipped and not by the original circular-arc models.  For a suitable clique K,
all circular-arc models of G with certain properties lead to the same interval graph <cit.>; see also <cit.>.
It thus makes sense to denote it as G^K.
He presented an algorithm to find a suitable set K and constructed the graph directly from G, without a circular-arc model.
As we have seen, the construction is very simple when G is chordal <cit.>.
In particular, the closed neighborhood of every simplicial vertex can be used as the clique K <cit.>.

If G is a circular-arc graph, then for any simplicial vertex s, the graph G^N[s] is an interval graph.  This explains why the graph ⊗(a_0, a_1, …, a_2 p - 1) is not a circular-arc graph when ℓ = ∑^2 p - 1_i=0 a_i≥ 4.
The graph (⊗(a_0, a_1, …, a_2 p - 1))^N[c] contains a hole of length ℓ; see appendix for more details.



However, G^K being an interval graph does not imply that G is a circular-arc graph.
There are restrictions on the intersection patterns of the intervals.
We <cit.> have fully characterized this correlation when G is C_4-free: it is a circular-arc graph if and only if G^K is an interval graph with no certain configurations (the list is reproduced in Section <ref>).
We use forbidden configurations to refer to minimal non-interval graphs and the configurations.

The task is then to “reverse” the construction to get all possible graphs G such that G^K contains a forbidden configuration.
One complexity is that each forbidden configuration corresponds to a large number of graphs, and the argument has to be based on case analyses.
To make it worse, there are seven families of infinite forbidden configurations: holes, † graphs,  graphs, and four infinite families of interval forbidden configurations, which can be viewed as variations of † graphs and  graphs.

We show that if G^N[s] contains a hole, then G must contain an ⊗ graph with ℓ≥ 4 or a graph S_k^+, k ≥ 4, i.e., the graph obtained from S_k by adding a vertex and making it adjacent to all the vertices of degree 2k -3 (solid nodes in Figure <ref>).[In a sense, the graphs S_k^+ can be viewed as ⊗(k).  We may twist the definition of ⊗ graphs to include them.  We use the current one for the purpose of simplicity.]
The analyses of other small forbidden configurations lead to eight small forbidden induced subgraphs.
Interestingly, none of the other infinite families of forbidden configurations leads to any new forbidden induced subgraph.
Indeed, for each of them, we can find an induced subgraph G' of G and a simplicial vertex s' of G' such that (G')^N[s'] contains a hole or a small forbidden configuration.
The main trick is to decrease the number of cases to be considered, especially finding the subgraph G' and vertex s' for infinite forbidden configurations.

The main result of the present paper is as follows.
For a graph G, we use G^⋆ to denote the graph obtained from G by adding an isolated vertex. 




  A chordal graph is a circular-arc graph if and only if it does not contain an induced copy of long claw, whipping top^⋆, a graph in Figure <ref>, S_k^+, k ≥ 3, or an ⊗ graph.




We also characterize chordal graphs that are not Helly circular-arc graphs.
We use the Venn diagram in Figure <ref> to illustrate the relationship of these classes.
Joeris et al. <cit.> showed that region 1 comprises all the complements of k-suns, and we <cit.> have previously settled regions 2 and 3. 


  A split graph is a circular-arc graph if and only if it does not contain an induced copy of any graph in Figure <ref>–<ref>, S_k^+, k ≥ 3, or ⊗(a, b) with 1 ≤ b ≤ 2 ≤ a.


Theorem <ref> summarizes all graphs in regions 2–5.
Note that all ⊗ graphs are in Regions 2 and 4 by Proposition <ref>, and a chordal forbidden induced subgraph of circular-arc graphs is in region 3 or 5 if and only if it contains an induced copy of some graph in region 1.
Interestingly, region 5 comprises a single graph.





  Region 4 comprises long claw, whipping top^⋆, the graph in Figure <ref>, ⊗(a, b), b ≥ 3, and ⊗(a_0, a_1, …, a_2 p - 1) with p ≥ 2.
  Region 5 comprises only the graph in Figure <ref>.


Regions 1, 2, and 4 together are the minimal chordal graphs that are not Helly circular-arc graphs.

  A chordal graph is a Helly circular-arc graph if and only if it does not contain an induced copy of long claw, whipping top^⋆, a graph in Figures <ref>, <ref>, <ref>, S_k, k ≥ 3, or an ⊗ graph.


Let us put our work into context.  By imposing restrictions on the intersection pattern between arcs, more than a dozen subclasses of circular-arc graphs have been defined and studied in the literature <cit.>.
Several of them have been characterized by forbidden induced subgraphs.
They are mostly in the lower levels of the class hierarchy.
The class of chordal circular-arc graphs is the second subclass that contains all interval graphs, and the only previous one was normal Helly circular-arc graphs <cit.>.  The characterizations of both subclasses are achieved through connecting the forbidden induced subgraphs and minimal non-interval graphs.



§ PRELIMINARIES


All graphs discussed in this paper are finite and simple.  The vertex set and edge set of a graph G are denoted by, respectively, V(G) and E(G).
For a subset U⊆ V(G), we denote by G[U] the subgraph of G induced by U, and by G - U the subgraph G[V(G)∖ U], which is shortened to G - v when U = {v}.
The neighborhood of a vertex v, denoted by N_G(v), comprises vertices adjacent to v, i.e., N_G(v) = { u | uv ∈ E(G) }, and the closed neighborhood of v is N_G[v] = N_G(v) ∪{ v }.
We may drop the subscript if the graph is clear from the context.
The complement graph G of a graph G is defined on the same vertex set V(G), where a pair of distinct vertices u and v is adjacent in G if and only if u v ∉E(G).

A clique is a set of pairwise adjacent vertices, and an independent set is a set of vertices that are pairwise nonadjacent. 
A graph is a split graph if its vertex set can be partitioned into a clique and an independent set.
We say that a vertex v is simplicial if N[v] is a clique; such a clique is necessarily maximal. 
A hole is an induced cycle of length at least four.

Let G be a chordal graph.
For each simplicial vertex s of G, we can use the clique N[s] to define the auxiliary graph G^N[s].
We use G^s as a shorthand for G^N[s].
The vertex set of G^s is  V(G), and the edge set is defined as follows.[The definition of G^s is different from <cit.>, where two vertices u, v∈ N_G[s] might be adjacent in G^s because u v is an edge of a C_4 in G.  They are equivalent on C_4-free graphs.]


  * The edges among vertices in V(G)∖ N_G[s] are the same as in G.

  * A pair of vertices u, v∈ N_G[s] are adjacent in G^s if there exists a vertex adjacent to neither of them, i.e., N_G(u)∪ N_G(v) V(G).

  * A pair of vertices u∈ N_G[s] and v∈ V(G)∖ N_G[s] are adjacent in G^s if N_G[v]⊈N_G[u].

Two quick remarks on the conditions are in order.
First, note that N(u)∪ N(v) = V(G) if and only if N[u]∪ N[v] = V(G) and uv∈ E(G).
Second, N_G[v]⊈N_G[u] if and only if either they are not adjacent, or there exists a vertex adjacent to v but not u in G.



Having two or more graphs on the same vertex set demands caution when we talk about adjacencies.  The only exception is the adjacency between a pair of vertices in V(G)∖ N_G[s].  Since such a pair has the same adjacency in G and G^s, we omit specifying the graph to avoid unnecessary clumsiness.

We now relate the main result of <cit.>.
Each graph in Figure <ref> carries annotations.  Some vertices are earmarked from N_G(s) or from V(G)∖ N_G[s], and some edges between N_G(s) and V(G)∖ N_G[s] are annotated.
Note a normal graph can be viewed as an annotated graph with no annotations.


The graph G^s contains an annotated copy of an annotated graph F if there exists an isomorphism φ between F and an induced subgraph of G^s with the following properties.

  
  * If v∈ N_G(s) then φ(v)∈ N_G(s).
  
  * If v∈ V(G)∖ N_G[s] then φ(v)∈ V(G)∖ N_G[s].
  
  * If an edge v u is annotated, then φ(v) φ(u) is an edge of G.  



By a forbidden configuration we mean a minimal non-interval graph or a graph in Figure <ref>. Note that the vertex s is not involved in any forbidden configuration of G^s.  Since it is universal in G^s, it cannot be in any minimal non-interval subgraph.
Most forbidden configurations in Figure <ref> do have universal vertices, but each universal vertex in them is the end of an annotated edge, which cannot happen for s.


The following are equivalent on a chordal graph G.
  
  
  * The graph G is a circular-arc graph.
  
  * For every simplicial vertex s, the graph G^s does not contain any annotated copy of forbidden configurations.

  * There exists a simplicial vertex s such that G^s does not contain any annotated copy of forbidden configurations.







§ THE PROOF


Throughout this section G is a chordal graph with no universal vertices and
we fix an arbitrary simplicial vertex s of G.
We rely on the reader to check the small graphs listed in Theorem <ref>, namely, long claw, whipping top^⋆, and those in Figure <ref>,
are minimal forbidden induced subgraphs.
It is also easy to check graphs S_k^+, k ≥ 3, thanks to the strong symmetries <cit.>.[A quick argument is as follows.
In S_k^+, every maximal clique is the closed neighborhood of some simplicial vertex.
Thus, if S_k^+ is a circular-arc graph, then it has to be a Helly circular-arc graph, but it is already known that S_k is not <cit.>.  The minimality follows from a similar observation.]
It is not that straightforward to show that all the ⊗ graphs are minimal forbidden induced subgraphs of circular-arc graphs.  
We defer the proof of Proposition <ref> to the appendix.
The rest of this section is focused on the sufficiency of Theorem <ref>, i.e., the completeness of this list.
By Theorem <ref>, if G is not a circular-arc graph, then G^s contains an annotated copy of a forbidden configuration.
By translating forbidden configurations in G^s back to graphs in G, we show that G must contain an induced copy of some graph listed in Theorem <ref>.
The trivial case is on forbidden configurations disjoint from N_G(s), which are necessarily non-interval graphs.

 
If G^s - N_G[s] is not an interval graph, then G contains an induced long claw, net^⋆, whipping top^⋆, ⊗(1, a), a ≥ 3, or ⊗(2, a), a ≥ 1.


By construction, G - N_G[s] and G^s - N_G[s] are isomorphic.  Thus, G contains a minimal non-interval graph; let U be its vertex set.
  We are done if G[U] is a long claw or a † graph on seven or more vertices; i.e., ⊗(1, a), a ≥ 3.  Otherwise, since G is chordal, G[U] is a net, whipping top, or a  graph by Theorem <ref>.  Thus, G[U∪{s}] is isomorphic to net^⋆, whipping top^⋆, or ⊗(2, a), respectively.  

For other forbidden configurations, we need vertices not in them.
For example, the subgraph of G induced by the four vertices in Figure <ref> is also a claw, hence a circular-arc graph.  As a matter of fact, any graph on four vertices are circular-arc graphs.  There are other vertices that help the formation of the forbidden configurations, though they are invisible in the forbidden configurations.


  An edge of G^s is collateral if it is an egde of G and at least one of its ends is in N_G[s].

Note that no edge among V(G)∖ N_G[s] is collateral.
If one end v of an edge is in N_G[s], then the edge is not collateral if and only if the other end is adjacent to neither s nor v in G.
Let v_1 v_2 be a collateral edge.
By construction there must be a vertex adjacent to neither of them when v_1, v_2∈ N_G[s], or a vertex in N_G[v_2]∖ N_G[v_1] when only v_1 is in N_G[s].
In other words, there is always a vertex w∈ V(G)∖ N_G[s] such that w v_i∈ E(G), i = 1, 2, if and only if v_i∉N_G[s].
The vertex w can be viewed as a “witness” of this edge.
We can generalize the concept of witnesses to any clique K of G^s.

  Let K be a clique of G^s.
  A vertex w∈ V(G)∖ N_G[s] is a witness of K (in G^s) if N_G[w]∩ K and N_G[s]∩ K partition K.
When K comprises the two ends of an edge of G^s, we say that w is a witness of the edge (in G^s).
  The clique or edge is then witnessed by w (in G^s).

When the graph G^s is clear from context, we usually omit its reference.
Let w be a witness of a clique K.
By definition, no edge between w and K is collateral.
We remark that the witness of a clique can be from this clique.
Indeed, if w∉K, then w is a witness of K∪{w}, which is a clique of G^s by construction.
Another remark is that every collateral edge needs a witness, but a witnessed edge may or may not be collateral.
Table <ref> lists some simple examples (note that the meaning of lines are different from forbidden configurations in Figure <ref>).



As said, when dealing with a forbidden configuration F, we need to take witnesses of the collateral edges within F into consideration.
A witness of one particular collateral edge might be adjacent to additional vertices in F, and witnesses of distinct collateral edges could either be adjacent or not.
These relationships pose significant challenges in our analysis.
To mitigate these complexities, we will introduce a series of observations.
The first of these is quite intuitive: note that two simplicial vertices are adjacent if and only if they have the same closed neighborhood. 


  Let K be a clique of G^s such that K⊆ N_G(s).
  
  
  * If K is witnessed, then it has a witness that is simplicial in G. 
  * If K is not witnessed, then G^s contains an induced sun. 


(i) We fix a clique tree of G, and root it at N_G[s].  Let w be a witness of K.  We take an arbitrary maximal clique K' of G that contains w.  No maximal clique in the subtree rooted at K' contains any vertex from K.  We can find a leaf node and take a vertex x that appears only in this node.  The vertex x is simplicial in G.


(ii) Let K' be a minimal subset of K that is unwitnessed.
  Note that |K'| > 2: by assumption, G does not contain a universal vertex; a clique of two vertices are the endpoints of an edge and hence has a witness by construction.
  We take three vertices v_1, v_2, and v_3 from K'.
  By the selection of K', for each i = 1, 2, 3, the clique K'∖{v_i} has a witness x_i.
  We may assume x_i, i = 1, 2, 3, is simplicial in G, and hence they are pairwise nonadjacent.
Since x_i is not a witness of K', it cannot be adjacent to v_i in G^s (we are using the fact that x_i is simplicial in G).
  Then G^s[{v_1, v_2, v_3, x_1, x_2, x_3}] is a sun.


Each collateral edge has one or more witnesses, and we designate one as the (designated) witness of this edge.  For a collateral edge between two vertices in N_G(s), we always designate a simplicial vertex of G (Lemma <ref>).

 

As shown in Figure <ref>, neither assertion of Lemma <ref> holds for cliques of G^s intersecting V(G)∖ N_G[s].
The next three propositions are on witnesses of edges and cliques involving vertices in V(G)∖ N_G[s].  The first is about vertices in N_G[s] and their non-neighbors in G.



Let v be a vertex in N_G[s].  For each vertex x∈ V(G)∖ N_G[v], it holds N_G^s[x]⊆ N_G^s[v].


Note that x∉N_G[s] because N_G[s]⊆ N_G[v] by the definition of simplicial vertices.
  Suppose for contradiction that there exists a vertex y∈ N_G^s[x]∖ N_G^s[v].
Note that y∈ N_G(s)∩ N_G(x); otherwise, v y must be an edge of G^s, witnessed by x.
By construction, there must be a witness w of the edge x y.
  Note that w∈ N_G(v), as otherwise it witnesses the edge v y.
  But then x w v y is a hole of G, a contradiction.


We consider next the subgraphs of G corresponding to connected induced subgraphs of G^s of order three.
It is trivial when none of the three vertices is from N_G(s).
Lemma <ref> has characterized the case when they are all from N_G(s) and form a clique in G^s.
The next statement is about a triangle of G^s with two vertices from N_G(s); see the second and third groups in Table <ref>.


  Let {v_0, v_1, v_2} be a clique of G^s with v_1, v_2∈ N_G(s) and v_0∈ V(G)∖ N_G[s].
  If the clique {v_0, v_1, v_2} is not witnessed, then it is a clique of G.


Since v_0 is not a witness of {v_0, v_1, v_2}, it is adjacent to at least one of v_1 and v_2 in G.
  Assume without loss of generality that
v_0∈ N_G(v_1).  By construction, there is a witness w_2 of v_0 v_1; hence w_2∈ N_G(v_0)∖ N_G[v_1]. Since w_2 does not witness {v_0, v_1, v_2}, it is adjacent to v_2 in G.
  Then v_0 and v_2 must be adjacent in G because it is chordal; otherwise, w_2 v_0 v_1 v_2 is a hole.


The last observation is on two collateral edges with different witnesses sharing a vertex.


  Let v_1 v_0 v_2 be a path of G^s such that both edges v_0 v_1 and v_0 v_2 are collateral and |{v_1, v_2}∩ N_G(s)|  1.
  
  
  * If v_0 v_1 and v_0 v_2 have a common witness, then v_1 v_2∈ E(G); and
  
  * otherwise, there is no edge between a witness of v_0 v_1 and a witness of v_0 v_2.
  


  (i) Let w be a common witness of v_0 v_1 and v_0 v_2.
  If v_1, v_2∈ N_G(s), then they are adjacent in G because N_G(s) is a clique. Now suppose v_1, v_2∉N_G(s); then v_0∈ N_G(s).
  Since v_1 v_0 v_2 w is not a hole of G, vertices v_1 and v_2 must be adjacent.


  (ii)  For i = 1, 2, let w_i be a witness of v_0 v_3-i.
By assumption, w_i is not a witness of v_0 v_i.
  In particular, w_1 w_2.
  Suppose for contradiction that w_1 and w_2 are adjacent.
  If v_1, v_2∈ N_G(s), then v_1 v_2 w_2 w_1 is a hole of G.
  In the rest, v_1, v_2∉N_G(s).
  Since w_i, i = 1, 2, does not witness the edge v_0 v_i, it is neither identical nor adjacent to v_i.
Depending on whether v_1 and v_2 are adjacent, either v_1 v_2 w_1 w_2 or v_1 v_0 v_2 w_1 w_2 is a hole of G, contradicting that G is chordal.


In the disposition of a forbidden configuration of G^s,
a simple but important trick is to focus on a “minimal” set of vertices that are required for the formation of the forbidden configuration under concern.  As long as we keep the vertex set of the forbidden configuration, a witness for each collateral edge in it, and the simplicial vertex s, we still have the same forbidden configuration. Note that removing a vertex may remove collateral edges, of which the vertex is the only witness, but it will never introduce new edges to the auxiliary graph.
The operation of keeping only a minimal set of vertices is especially handy if the resulting subgraph of G is a split subgraph, because we <cit.> have characterized all forbidden induced subgraphs that are split graphs.
Another natural idea is to assume that there is no any forbidden configuration that has been discussed.
Formally, we introduce the following assumptions.




  Induction For any vertex set A⊆ V(G) and any simplicial vertex x of the subgraph G[A], the graph (G[A])^x does not contain an annotated copy of any forbidden configuration discussed previously.  

  Minimality For any vertex set A with s∈ A⊊ V(G), the graph (G[A])^s does not contain any annotated copy of the forbidden configuration under discussion.  


These assumptions greatly simplify our discussions.
For example, they have the following implications.


  Under the assumptions Induction and Minimality, the following hold when we discuss a forbidden configuration F.

 
  *  For every simplicial vertex x of G, the subgraph G - N[x] is an interval graph.

  * 
  Every annotated copy of F in G^s contains all the vertices in N_G(s).

  * 
  Let G^s[U] be an annotated copy of F, and x a simplicial vertex of G^s[U].
  If x is not annotated, then there cannot be a witness w of N_G^s[x]∩ U such that x w and N_G^s[x]∩ U = N_G^s[w]∩ U.



  P<ref> follows from Induction.  If G - N[x] is not an interval graph, then G^x contains an induced non-interval graph disjoint from N_G[x], which has been discussed in Proposition <ref>.

  P<ref> follows from Minimality.
  Suppose for contradiction that there is a vertex set U such that N_G(s)⊈U and G^s[U] is an annotated copy of F.
  Then, the subgraph of (G - N_G(s)∖ U)^s induced by U is an annotated copy of forbidden configuration as F.

  P<ref> follows from Minimality.
  If such a vertex w exists, then the graph (G - x)^s still contains an annotated copy of F, with x replaced with w.  Note that N_G^s[w]∩ U is a clique, and no edge in G^s[U] outside this clique is witnessed by x.

  
We start with holes and the sun.


  If G^s is not chordal, then G contains an induced copy of S_ℓ^+ with ℓ≥ 4 or ⊗(a_0, a_1, …, a_2 p - 1) with ∑ a_i≥ 4.


Let U be the vertex set of a hole of G^s.
  We number vertices in U such that the hole is v_0⋯ v_|U| - 1.
  In this proof, indices of vertices in U are modulo |U|.
  Note that for each vertex v_i∈ U∩ N_G(s), both edges v_i - 1 v_i and v_iv_i + 1 are collateral by Proposition <ref>.
  For i = 0, …, |U| - 1, 
if v_i v_i+1 is a collateral edge, let w_i be its witness.
Let W denote the set of witnesses.
By Minimality,
  
    V(G) = U∪ W∪{s}.

  
  First, we argue that the witness w_i of a collateral edge v_i v_i+1 does not have other neighbors on this hole in G^s.
  That is,
  
    N_G^s(w_i) ∩ U = {v_i, v_i+1}.

  We may assume v_i∈ N_G(s), and the other is symmetric.
  By Proposition <ref>, N_G^s(w_i) ∩ U⊆{v_i-1, v_i, v_i+1}.
  If v_i-1∈ N_G^s(w_i), then replacing v_i with w_i in U leads to another hole, violating P<ref>.


  Second, we argue that
  
    W is an independent set (in both G and G^s).

  Suppose for contradiction that there are distinct i, j∈{0, …, |U| - 1} such that w_i w_j∈ E(G).
  If both v_i and v_i+1 are from N_G(s), then {v_i, v_i+1}⊆ N_G^s(w_j) by Proposition <ref>.  Since {v_i, v_i+1}{v_j, v_j+1}, we have a contradiction to (<ref>).
  It is similar when both v_j, v_j+1∈ N_G(s).
  Thus, only one of {v_i, v_i+1}  and only one of {v_j, v_j+1} are in N_G(s).
  We may assume without loss of generality that v_j is from N_G(s) and v_j+1 is not.
  Note that v_j⊆ N_G^s(w_i) by Proposition <ref> and v_i = v_j - 1 by (<ref>).
This contradicts Proposition <ref>(ii), applied to the path v_j - 1 v_j v_j + 1.

  
  If U⊆ N_G(s), then U∪{s} is a clique, and G is a split graph by (<ref>) and (<ref>).  Thus, G contains an induced S_|U|^+ <cit.>.
In the rest, U contains vertices from both N_G(s) (by P<ref>) and V(G)∖ N_G[s].
  Note that the number of edges on the hole between N_G(s) and V(G)∖ N_G[s] is even.
  Let it be 2 p for some positive integer p.
  Removing all these 2 p edges from the hole leaves a sequence of (possibly trivial) paths.
  For i = 0, 1, …, 2 p-1, let V_i denote the vertex set of the ith path.
  Note that V_i is either a subset of N_G(s) or disjoint from V(G)∖ N_G[s], and if V_i⊆ N_G(s), then V_i+12 p⊆ V(G)∖ N_G[s], and vice versa.
We may assume without loss of generality that V_0⊆ N_G(s).  Hence,

    N_G(s) = V_0∪ V_2∪⋯∪ V_2p - 2.
  
For i = 0, …, p - 1, all the edges on the hole incident to V_2 i are collateral (Proposition <ref>); let W_2i denote these |V_2i|+1 witnesses.
  Note that W = W_0∪ W_2∪⋯∪ W_2 p - 2.
Two of the witnesses are adjacent to V_2i-12 p and V_2i+1, and let them be w_2i^1 and w_2i^2, respectively.
  The subgraph G[V_2i∪ W_2i] is the gadget D_|V_2i|, the ends of which are w_2i^1 and w_2i^2.
  On the other hand, G[V_2i+1] is the same simple path as G^s[V_2i+1].
  The vertices in V_2 i are complete to vertices not in this gadget, while the two ends of G[V_2i+1] are connected to w_2i^2 and w_2i+22 p^1, respectively.
Thus, G is isomorphic to ⊗(|V_0|, |V_1|, …, |V_2p - 1|), with c = s.





  If G^s contains an induced sun, then G contains an induced copy of a graph specified in Theorem <ref>.


  Let U denote the vertex set of the sun, and we number them as follows.
  The degree-four vertices are v_0, v_1, and v_2, and for i = 0, 1, 2, the only vertex in U∖ N_G^s[v_i] is x_i.
  We claim that
  
    {v_0, v_1, v_2}∩ N_G(s)∅.

  Suppose for contradiction that {v_0, v_1, v_2} is disjoint from N_G(s).
By P<ref>, {x_0, x_1, x_2}∩ N_G(s)∅.
  Assume without loss of generality that x_0∈ N_G(s).
  We note that {v_1, v_2, x_0} is not witnessed; if w is a witness of {v_1, v_2, x_0}, then N_G^s(w) ∩ U = {v_1, v_2, x_0} by Proposition <ref>, violating P<ref>.
  For i = 1, 2, let w_i be the witness of the edge x_0 v_i; note that N_G^s(w_i)∩ U = {x_0, v_i} by Proposition <ref>.
  By Proposition <ref>(ii), w_1 and w_2 are not adjacent.
But then (G - {x_1, x_2})^s contains a sun, violating Minimality.

  By Proposition <ref>, the set {v_0, v_1, v_2} is always a clique in G.
  Thus, an edge among {v_0, v_1, v_2} is collateral if and only if at least one of its ends is in N_G[s].
For distinct i, j∈{0, 1, 2}, let w_ij be the witness of the edge v_i x_j if it is collateral, and let W denote the set of witnesses.
  Note that U and W are disjoint by Proposition <ref>.
  We claim that
  
    V(G) = U∪ W∪{s}.

  Let H= (G[U∪ W∪{s}])^s.
  By construction, H[U] is a subgraph of G^s[U], in which all the edges incident to x_i, i∈{0, 1, 2}, are present.
  By Induction, H[U] is chordal, which means that {v_0, v_1, v_2} is a clique.


  Let i and j be two distinct indices in {1, 2, 3}, and let k = 3-i-j.  We note that 

    w_i j v_j∈ E(G) if and only if v_j∈ N_G(s).

  It follows from Proposition <ref> when neither v_j nor x_j is in N_G(s), or Proposition <ref> otherwise.  As a result, if v_i v_j is collateral, then its witness must be from {x_k, w_i k, w_j k}.
  Note that if x_k is a witness of v_i v_j, then neither v_i x_k nor v_j x_k is collateral, and hence x_k is the only witness of v_i v_j.
  In the rest, we show that this is always the case.
  Suppose that v_i v_j is a collateral edge and let w be its witness.

  We claim that
  
    w = x_k.

  We start with showing that
  
    if w x_k, then {w_i k, w_j k} = {w}, v_k∈ N_G(s) and w v_k∈ E(G^s).

  Note that when x_k is not a witness of v_iv_j, at least one of v_i x_k and v_j x_k is collateral.
  The other may or may not be collateral, and hence one of w_i k and w_j k is undefined.
  We may assume without loss of generality that v_i∈ N_G(s).
  By (<ref>) and (<ref>), w∈{w_i k, w_j k}.
  In either case, w is a witness of {v_i, v_j, x_k}.
  By Minimality, w is the witness of both edges v_i x_k and v_j x_k, if collateral.
  By P<ref>,

    {v_i, v_j, x_k}⊊ N_G^s(w).

  By Proposition <ref>, N_G^s(w)∩ U⊆ U∖{x_i}.
  If v_k∉N_G^s(w), then v_j ∈ N_G^s(w) and w v_j v_k x_j is a hole of G^s, violating Induction.
  Thus, v_k∈ N_G^s(w) and v_k∈ N_G(s) by (<ref>).
  This concludes (<ref>).
  
  By (<ref>), w v_k is collateral and needs a witness w'.
  Now that all the edges among v_1, v_2, and v_3 are collateral, each vertex in W is a witness of some of them.  
Since w'∈ N_G^s(v_k)∩ N_G^s(w), it cannot be x_i (recall that v_i∈ N_G(s)).
  If w' is a witness of v_j v_k, then w w' v_i v_k is a hole of G by (<ref>) (with indices switched).
If w' = x_j, then (G - v_i)^s contains an induced sun, with v_i replaced by w, violating Minimality.
  If none of above is true, w' has to be a witness of v_i v_k and is different from x_j.
  Then w w' v_j v_k is a hole of G by (<ref>) (note that v_j∈ N_G(s) and it is symmetric to the previous one).
  Thus, (<ref>) must be true, and x_k is the only witness of v_i v_j.
  


  We will see that G is always a split graph.
  If two or more in {v_0, v_1, v_2} are from N_G(s), then {x_0, x_1, x_2}⊆ V(G)∖ N_G[s], and V(G) = U∪{s}.  Thus, G is a split graph, with the clique {v_0, v_1, v_2}.
Hence, assume without loss of generality that v_0∈ N_G(s), while v_1 and v_2 are not.
  If x_0∉N_G(s), then V(G) = U∪{s}, and G is again a split graph, with the clique {v_0, v_1, v_2}.
In the rest, x_0∈ N_G(s). By Proposition <ref>, both v_1 and v_2 are adjacent to x_0 in G.
  By P<ref> and Proposition <ref>, the clique {v_1, v_2, x_0} cannot be witnessed.
  Note that w_1 0 and w_2 0 are not adjacent by Proposition <ref>.
  Hence, V(G) = U∪{s, w_1 0, w_2 0}, and G is again a split graph, with the clique {v_0, v_1, v_2, x_0}.


After the sun, the assumptions enable us to impose a further constraint on simplicial vertices of forbidden configurations.
As one can easily observe from Figure <ref>,
a simplicial vertex in a minimal non-interval graph has degree at most two.
In each forbidden configuration in Figure <ref>, a simplicial vertex has at most three neighbors, and all simplicial vertices with three neighbors have been annotated to be from V(G)∖ N_G[s].
Please be reminded that a simplicial vertex of a forbidden configuration is not necessarily simplicial in G^s or G.


  Under the assumptions Induction and Minimality, the following hold when we discuss a forbidden configuration F.

   

  * 
  There is an annotated copy of F in G^s in which all simplicial vertices are from V(G)∖ N_G(s).



Let U be the vertex set of an annotated copy of F.  We have nothing to do if no simplicial vertex of G^s[U]  is from N_G(s).
  Suppose that a vertex v∈ N_G[s] is simplicial in G^s[U].
A quick check of the forbidden configurations convince us that |N_G^s(v)∩ U|≤ 2 and no vertex in N_G^s(v)∩ U is simplicial in G^s[U].  Thus, all the edges in G^s[U] incident to v are collateral.
  Let K = N_G^s[v]∩ U.
  We note that
  
    K is not witnessed.

  Otherwise, there is a witness w of K (by Lemma <ref>), and N_G^s(w)∩ U = K by Proposition <ref>.
 But then replacing v with w leads to an annotated copy of F with one fewer vertex from N_G(s), violating P<ref>.


 By (<ref>), N_G^s(v)∩ U consists of two vertices, and at least one of them is not in N_G[s].
Let N_G^s(v)∩ U = {x_1, x_2}.  A quick check of the forbidden configurations convince us that there always exists a vertex x_3 that is adjacent to x_1 and x_2 but not v in G^s.
   For i = 1, 2, we can find a witness w_i of the edge v x_i.  We argue that
   
    G^s[{v, x_1, x_2, x_3, w_1, w_2}]  is a sun,

   violating Induction.
   By Proposition <ref>, N_G^s(w_i)∩ U ⊆{v, x_1, x_2} for i = 1, 2. 
   They cannot be equal; otherwise, we can replace v with w_i, violating P<ref> (note that v is in N_G(s) and cannot witness any edge).
If w_1 and w_2 are adjacent, then x_1 x_2 w_2 w_1 is a hole in G^s.  This concludes (<ref>) and the proof.


We now deal with the remaining forbidden configurations one by one.
Thanks to P<ref>, we assume that no simplicial vertex for the forbidden configurations is from N_G[s].
We may separate one forbidden configuration into different incarnations.
In particular, we deal with the smallest ones of the infinite families (†, , and Figures <ref>–<ref>) separately.
For example,
the smallest of Figure <ref> are
Figures <ref> and <ref>.
Moreover, Figure <ref> is only a special incarnation of Figure <ref>, and the general one will be Figure <ref>.
Sometimes we group multiple forbidden configurations together, then Minimality applies to all of them.
Throughout we use U to denote the vertex set of an annotated copy of the forbidden configuration under discussion.




  For i = 1, 2, 3, let w_i be the witness of the edge v u_i.
  By Proposition <ref>, w_1, w_2, and w_3 are distinct, and there is no edge among them.
  By Minimality, V(G) = U∪{s, w_1, w_2, w_3}.
  The graph G-s is a long claw, where the vertex v has degree three.



  Since G^s does not contain an annotated copy of Figure <ref>,
  the edge u_1 v_2 is not collateral, and at most one of u_2 v_1 and u_3v_1 is collateral.
If neither u_2 v_1 nor u_3v_1 is collateral, then for i = 2, 3, we can find a witness w_i of the clique {u_i, v_1, v_2} (Proposition <ref>).
  By Proposition <ref>, w_2 and w_3 are not adjacent.
  Also note that neither of them is adjacent to u_1; otherwise, u_1 v_1 v_2 u_i w_i is a hole of G.
  Then G[U∪{w_2, w_3}] is a long claw, centered at v_2.
In the rest, assume without loss of generality that u_2 v_1 is collateral and u_3 v_1 is not.


  For i = 1, 3, we can find a witness w_i of the clique {u_i, v_1, v_2} by Proposition <ref>.
  Since G is chordal, w_1 and w_3 are distinct and nonadjacent.
  If the clique {u_2, v_1, v_2} has a witness w_2, then
  w_1 and w_2 are not adjacent by Proposition <ref> (considering the path u_1 v_1 u_2).
  In this case, G[U∪{w_1, w_2}] is isomorphic to Figure <ref>, where v_1 v_2 u_2 is the triangle, and u_1 has degree two.


  Now that the clique {u_2, v_1, v_2} is not witnessed, for i = 1, 2, let w'_i be the witness of the edge v_i u_2.
Since w'_i is not a witness of {u_2, v_1, v_2}, it must be adjacent to v_3 - i in G.
  By Proposition <ref>, w'_1 and w'_2 are not adjacent.
  By Proposition <ref>, neither w_1 and w'_1 nor w_3 and w'_2 can be adjacent.
  If w_3 and w'_1 are not adjacent, then G[{s, v_1, v_2, u_2, w'_1, w'_2, w_3}] is isomorphic to sun^⋆, where w_3 is the isolated vertex.  
  It is similar if w_1 and w'_2 are not adjacent.
  Otherwise, G[{s, v_1, u_2, w_1, w_3, w'_1, w'_2}] is isomorphic to Figure <ref>, where v_1 u_2 w'_2 is the triangle and w'_1 has degree two.



  Since G^s does not contain an annotated copy of Figure <ref>, for i,j∈{1, 2, 3}, the edge u_i v_j is collateral if and only if i = j.
  Thus, G[U∪{s}] is an S_3^+.


Figures <ref> and <ref> are the smallest incarnations of Figure <ref>, whose general case will be discussed as Figure <ref>.
Figure <ref> is the first example of Figure <ref>, and the other is Figure <ref>.
We discuss the forbidden configurations in Figures <ref> and <ref> as a group, because they reduce to each other.  




We separate Figure <ref> into two cases, depending on whether one of edges v x_1 and v x_2 is collateral.

  We start with Figure <ref> in which neither v x_1 nor v x_2 is collateral.  Note that for i = 1, 2, the vertex x_i is a witness of the edge v u_i.
We argue that the edge v x_0 is not collateral.
Suppose for contradiction that x_0 v∈ E(G), and let w be the witness of v x_0.
  By Proposition <ref> (considering the path x_0v u_1), w is not adjacent to u_1 (note that w is a witness of v u_1 if w and u_1 are adjacent).
By Proposition <ref>(ii), x_1 is not adjacent to w.
  By symmetry, u_2, x_2∉N_G(w).
  Thus, N_H(w)∩ U = {v, x_0}, violating P<ref>.

  By Minimality, V(G) = U∪{s}.
  Then G is isomorphic to net^⋆, where x_0 is isolated.

  We then consider Figure <ref>.
  Note that
  
    x_0 v is not collateral and x_1 v is collateral.

  First, if x_0 v is collateral, then G^s - x_1 is an annotated copy of Figure <ref>.
  Second, if x_1∉N_G(v), then it is a witness of both edges u_1 v and u_2 v, violating Proposition <ref>(i).


  If the clique {v, u_1, x_1} is not witnessed, we can find a witness w_1 of the edge v u_1 and a witness w_2 of the edge v x_1. 
  Note that neither w_1 x_1 nor w_2 u_1 is an edge of G, and w_1 and w_2 are not adjacent by Proposition <ref>(ii).
  Then G^s[{x_0, v, w_1, u_1, x_1, w_2}] is an annotated copy of Figure <ref>; note that w_1, w_2∉N_G(v).
  It is symmetric if {v, x_1, u_2} is not witnessed.
  Now that {v, u_1, x_1} and {v, u_2, x_1} are both witnessed, let w_1 and w_2 be witnesses of them, respectively.
  By Minimality, V(G) = U∪{s, w_1, w_2}.
  By Proposition <ref> (considering the path u_1 v u_2), none of u_1 w_2, w_1 u_2, and w_1 w_2 can be an edge of G.
  Thus, G is isomorphic to whipping top^⋆, where w_1 u_1 v u_2 w_2 is the path of length five, and the degrees of s, x_0, and x_1 are 1, 0, and 5, respectively.

  Finally, we consider Figure <ref> in which at least one of v x_1 and v x_2 is collateral.  
If v x_i, i = 1, 2, is collateral,
then G^s[U] - x_3 - i is an annotated copy of Figure <ref>.
  


  First, note that neither v x_1 nor v x_4 is collateral.
If v x_1 or v x_4 is collateral, then the subgraph G^s[U] - x_3 or G^s[U] - x_2, respectively, is an annotated copy of Figure <ref>.  
  In the graph (G[U∪{s}])^s, both edges v x_1 and v x_4 and edges on the path x_1 x_2 u x_3 x_4 are present. Since (G[U∪{s}])^s is chordal, all the edges v u, v x_2, and v x_3 must be present.
  By Minimality, V(G) = U∪{s}.
  The witness of v u must be from N_G(u)∩ U∖ N_G[s] = {x_2, x_3}.
  Assume without loss of generality that x_2 witnesses v u.
  Then
  
    {s, u}⊆ N_G(v) ⊆{s,u, x_3}.

  Note that x_1 x_2 u x_3 x_4 is a path in G.
  Then G is a long claw when x_3∉N_G(v), or isomorphic to Figure <ref> otherwise.


We show that this cannot happen: the existence of an annotated copy of Figure <ref> violates some assumption.


  Since G^s does not contains an annotated copy of Figure <ref>,
  
    the edge x_0 v is not collateral.

Suppose first that both {v, u_1, x_1} and {v, u_2, x_1} are witnessed.  For i = 1, 2, let w_i be a witness of {v, u_i, x_1}.  By Minimality, V(G) = U∪{s, w_1, w_2}.
  Then N_G(x_0) = {x_1}, and
  
    N_G[x_1] ∖{x_0}⊆ N_G[v] = {s, v, x_1, u_1, u_2}.

In the graph G^x_0, the path w_1 u_1 v u_2 w_2 is induced.
  Since neither w_1 nor w_2 is in N_G(x_1), the vertex x_1 is adjacent to u_1, u_2, w_1, and w_2 in G^x_0.
  Thus, either v u_1 x_1 u_2 is a hole in G^x_0, or G^x_0 - x_0 is an annotated copy of Figure <ref>, both violating Induction.


  In the rest, at least one of the triangles in G^s[U] is not witnessed.      
  Suppose without loss of generality that {v, u_1, x_1} is not witnessed.
  By Proposition <ref>, the edge u_1 x_1 is also collateral.
    We find witnesses w_1 and w_2 of the edges v u_1 and u_1 x_1, respectively.
    We also find a witness w_3 of the edge v u_2.
    Let w_4 = w_3 if w_3 witnesses the clique {v, u_2, x_1}, or a witness of edge u_2 x_1 otherwise (the edge u_2 x_1 must be collateral when the clique is not witnessed by Proposition <ref>).
    By Minimality,
    
    V(G) = U∪{s, w_1, w_2, w_3, w_4}.

    By Proposition <ref>, w_1 cannot be adjacent to w_2 (considering the path v u_1 x_1) or w_3 (considering the path u_1 v u_2).
    For the same reason, w_3 and w_4 are not adjacent when they are different.
    By Proposition <ref>, N_G^s(w_2)∩ U ⊆{v, u_1, u_2, x_1}.
    They being equal violates P<ref> (we can replace x_1 with w_2), and it violates P<ref> if N_G^s(w_2)∩ U = {v, u_1, x_1}.
    Since v∈ N_G^s(w_2) when u_2∈ N_G^s(w_2) (because G^s is chordal),
    
    N_G^s(w_2)∩ U = {u_1, x_1}.

    By Proposition <ref> (considering the path u_1 v u_2), w_1 and u_2 are not adjacent.
    Since G^s[U∪{w_1, w_2}∖{x_0}] is not an induced sun, w_1 x_1 is a collateral edge.
    Then w_1 and w_4 cannot be adjacent (considering the path w_1 x_1 u_2 when w_4 w_3).
    But then there cannot be a witness of w_1 x_1, a contradiction.


Figure <ref> is the net graph, i.e., the smallest incarnation of † graphs, and Figure <ref> is a smallest incarnation of Figure <ref>, with the edge v x_2 collateral.
Their general ones will be Figure <ref> and Figure <ref>, respectively.

