For \(0\le n\le 3\) , we will call the vertices along the `arm' at the angle \(\pi /2+2n\pi /3\)  by \(a_{n1}\)  and \(a_{n2}\)  where \(a_{n1}\)  is the neighbor of the center vertex and \(a_{n2}\)  is the outermost vertex on the given arm. We will denote the center vertex by \(c\) . We then have that the set \(A=\lbrace a_{n2}:0\le n\le 2\rbrace \)  is asteroidal in \(\mathrm {I}\) . By Lemma REF , any intersection graph having \(\mathrm {I}\)  as a subgraph must add an edge incident to one of the elements of \(A\) , so we will start our search for necessary edges here.
Let \(\mathbb {G}\)  be an intersection graph and \(i:\mathrm {I}\rightarrow \mathbb {G}\)  an injective graph homomorphism (we will denote \(i(a_{kj})\)  by \(a^{\prime }_{kj}\) ). We may assume that \(a^{\prime }_{02}\)  has an edge that does not occur in \(\mathbb {G}\)  since any permutation of \(A\)  can be achieved by a graph automorphism of \(\mathrm {I}\) . If \(a^{\prime }_{02}\mathrel {E}^{\mathbb {G}}a^{\prime }_{12}\)  then the set of vertices \(\lbrace a^{\prime }_{12},a^{\prime }_{02},a^{\prime }_{01},c^{\prime },a^{\prime }_{11}\rbrace \)  can be taken to form a subgraph of \(\mathbb {G}\)  isomorphic to \(\mathrm {III}_5\)  with the nodes labeled in the order given. From the necessary sets found for \(\mathrm {III}_n\) , one of the edges \(e_1:=\lbrace a^{\prime }_{02},a^{\prime }_{11}\rbrace ,\lbrace a^{\prime }_{12},a^{\prime }_{01}\rbrace ,e_2:=\lbrace a^{\prime }_{02},c^{\prime }\rbrace \)  must also appear in \(\mathbb {G}\) . We note that the first two edges differ by an automorphism of \(\mathrm {I}\)  so we may treat only one of them explicitly (note that the proposed necessary set is stable under automorphism of \(\mathrm {I}\) ). If the edge \(e_1\)  is in \(\mathbb {G}\) , then the set \(\lbrace a^{\prime }_{02},a^{\prime }_{11},c^{\prime },a^{\prime }_{01}\rbrace \)  forms a subgraph isomorphic to \(\mathrm {III}_4\) , which means that either \(e_2\)  or \(e_3=\lbrace a^{\prime }_{11},a^{\prime }_{01}\rbrace \)  appear in \(\mathbb {G}\) .
Thus the statement that either \(e_1\)  or \(e_2\)  appears in \(\mathbb {G}\)  can be reduced to the statement that either \(e_2\)  or \(e_3\)  (the dotted edges) appear in \(\mathbb {G}\) . To show the desired result it will be enough to check that there are two intersection graphs having \(\mathrm {I}\)  as a subgraph with the edge \(e_2\)  but not \(e_3\)  and vice versa. To do this, we note that the following two graphs are interval intersection graphs in \(\mathbb {R}\)  (with labels indicating a possible set of intervals with the given intersection graph):
\(\hbox{\begin{tikzpicture} [circle dotted/.style={line width = 0.3mm, dash pattern= on .05mm off 1mm, line cap = round}, scale=2]{enclosed/.style={draw, circle, inner sep=0pt, minimum size=.1cm, fill=black}}\end{tikzpicture}\node [enclosed, label={[label distance=-1.25mm, xshift=-.45mm, yshift=-.5mm]176:\tiny $(4{,}\,9)$}] (1) at (0,0) {};\node [enclosed, label={[label distance=-0.75mm]left:\tiny $(6{,}\,7)$}] (2) at (0,.75*0.5) {};\node [enclosed, label={[label distance=-0.75mm]left:\tiny $(6{,}\,7)$}] (3) at (0,1.5*0.5) {};\node [enclosed, label={[label distance=-0.75mm, yshift=.5mm]left:\tiny $(2{,}\,5)$}] (4) at (-0.65*0.5,-0.375*0.5) {};\node [enclosed, label={[label distance=-0.75mm]left:\tiny $(1{,}\,3)$}] (5) at (-1.3*0.5,-.75*0.5) {};\node [enclosed, label={[label distance=-0.75mm, yshift=.5mm]right:\tiny $(8{,}\,11)$}] (6) at (0.65*0.5,-0.375*0.5) {};\node [enclosed, label={[label distance=-0.75mm]right:\tiny $(10{,}\,12)$}] (7) at (1.3*0.5,-.75*0.5) {};}(1) -- (2);(2) -- (3);(1) -- (4);(4) -- (5);(1) -- (6);(6) -- (7);(1) edge[bend right = 60] (3);\) 
         
\(The other edges belong in the \) 
\(-minimal necessary set by symmetric arguments.\)
Lemma 8.13 The dotted edges in
\(\hbox{\begin{tikzpicture} [circle dotted/.style={line width = 0.3mm, dash pattern= on .05mm off 1mm, line cap = round}]{enclosed/.style={draw, circle, inner sep=0pt, minimum size=.1cm, fill=black}}\end{tikzpicture}\node [enclosed, label={[label distance=0mm,xshift=-1mm,yshift=-.2mm]290:$v_4$}] (1) at (0,0) {};\node [enclosed, label=below:$v_3$] (2) at (-0.75*1,0) {};\node [enclosed, label=below:$v_2$] (3) at (-1.5*1,0) {};\node [enclosed, label=right:$v_1$] (4) at (0,0.75*1) {};\node [enclosed, label=below:$v_5$] (5) at (0.75*1,0) {};\node [enclosed, label=below:$v_6$] (6) at (1.5*1,0) {};\node [enclosed, label=right:$v_7$] (7) at (0,-.75*1) {};}(1) -- (2);(2) -- (3);(1) -- (5);(5) -- (6);(4) -- (1);(4) -- (2);(4) -- (3);(4) -- (5);(4) -- (6);(1) -- (7);\) 
[circle dotted] (4) edge[bend right = 110, looseness = 4] (7);
[circle dotted] (1) edge[bend right = 60] (3);
[circle dotted] (2) edge[bend left = 30] (5);
[circle dotted] (1) edge[bend left = 60] (6);
\(form a necessary set of minimal cardinality for \) 
II\( in \) L2\(.\)
As before, we recognize that the set \(A=\lbrace v_2,v_6,v_7\rbrace \)  is asteroidal in \(\mathrm {II}\)  and start our analysis with edges that are adjacent to elements of \(A\) . We start by noticing that the edges \(\lbrace v_2,v_4\rbrace ,\lbrace v_4,v_6\rbrace ,\)  and \(\lbrace v_1,v_7\rbrace \)  must be in any necessary set as \(\mathrm {II}\)  becomes an interval intersection graph in \(\mathbb {R}\)  when any one of these edges is added. For example, the collections of intervals given by:
\(\hbox{\begin{tikzpicture} [circle dotted/.style={line width = 0.3mm, dash pattern= on .05mm off 1mm, line cap = round}, scale=1.5]{enclosed/.style={draw, circle, inner sep=0pt, minimum size=.1cm, fill=black}}\end{tikzpicture}\node [enclosed, label={[label distance=0mm,xshift=-1mm,yshift=-.2mm]290:\tiny $(2{,}\,8)$}] (1) at (0,0) {};\node [enclosed, label=below:\tiny $(4{,}\,6)$] (2) at (-0.75*1,0) {};\node [enclosed, label=below:\tiny $(4{,}\,6)$] (3) at (-1.5*1,0) {};\node [enclosed, label={[yshift=-.5mm]above:\tiny $(5{,}\,10)$}] (4) at (0,0.75*1) {};\node [enclosed, label=below:\tiny $(7{,}\,10)$] (5) at (0.75*1,0) {};\node [enclosed, label=below:\tiny $(9{,}\,10)$] (6) at (1.5*1,0) {};\node [enclosed, label=right:\tiny $(1{,}\,3)$] (7) at (0,-.75*1) {};}(1) -- (2);(2) -- (3);(1) -- (5);(5) -- (6);(4) -- (1);(4) -- (2);(4) -- (3);(4) -- (5);(4) -- (6);(1) -- (7);\) 
(1) edge[bend right = 60] (3);
\((note that the case of the edge \) 
v4,v6}\( being added is symmetric to the case of \) {v2,v4}\().\) It remains to find any intersection graphs \(\mathbb {G}\)  with \(\mathrm {II}\)  as a subgraph and which fail to contain any of the edges so far found. The remaining choices for adding an edge incident to an element of \(A\)  are (up to symmetry) \(e_1=\lbrace v_2,v_7\rbrace \) , \(e_2=\lbrace v_2,v_5\rbrace \) , and \(e_3=\lbrace v_2,v_6\rbrace \) . Note that the edge \(\lbrace v_3,v_7\rbrace \)  (or the symmetric \(\lbrace v_5,v_7\rbrace \) ) can be added to \(\mathrm {II}\)  without changing the fact that \(A\)  is asteroidal. Thus another edge incident to an element of \(A\)  must be still be added to produce an intersection graph, allowing us to ignore the edge \(\lbrace v_3,v_7\rbrace \) .
Suppose first that an intersection graph \(\mathbb {G}\)  extends \(\mathrm {II}\)  and has the edge \(e_1\) . Then the vertices \(\lbrace v_1,v_4,v_7,v_2\rbrace \)  form a cycle of length 4, and so either the edge \(\lbrace v_1,v_7\rbrace \)  or the edge \(\lbrace v_2,v_4\rbrace \)  belong to \(\mathbb {G}\) . Both of these edges are already accounted for, so all intersection graphs with the edge \(\lbrace v_2,v_7\rbrace \)  are already accounted for.
Now suppose that \(\mathbb {G}\)  is an intersection graph containing the edge \(\lbrace v_2,v_5\rbrace \) . But then \(\mathbb {G}\)  contains the 4-cycle \(v_2,v_3,v_4,v_5\)  and so must contain either the edge \(\lbrace v_3,v_5\rbrace \)  or the edge \(\lbrace v_2,v_4\rbrace \) . The latter is already covered, so adding \(\lbrace v_3,v_5\rbrace \)  to the necessary set will cover all intersection graphs with the edge \(\lbrace v_2,v_5\rbrace \)  (and, by a symmetric argument, all intersection graphs with the edge \(\lbrace v_3,v_6\rbrace \) ). It remains to check that the edge \(\lbrace v_3,v_5\rbrace \)  occurs in an intersection graph not having any of the other edges in the proposed necessary set. The graph \(\mathrm {II}\)  with the edges \(\lbrace v_2,v_5\rbrace \)  and \(\lbrace v_3,v_5\rbrace \)  added accomplishes this goal. In particular, the collection of real intervals
\(\hbox{\begin{tikzpicture} [circle dotted/.style={line width = 0.3mm, dash pattern= on .05mm off 1mm, line cap = round}, scale=1.5]{enclosed/.style={draw, circle, inner sep=0pt, minimum size=.1cm, fill=black}}\end{tikzpicture}\node [enclosed, label={[label distance=0mm,xshift=-1mm,yshift=-.2mm]290:\tiny $(2{,}\,7)$}] (1) at (0,0) {};\node [enclosed, label=below:\tiny $(6{,}\,9)$] (2) at (-0.75*1,0) {};\node [enclosed, label={[xshift=.5mm]below:\tiny $(8{,}\,10)$}] (3) at (-1.5*1,0) {};\node [enclosed, label={[yshift=-.5mm]above:\tiny $(4{,}\,13)$}] (4) at (0,0.75*1) {};\node [enclosed, label=below:\tiny $(5{,}\,12)$] (5) at (0.75*1,0) {};\node [enclosed, label=below:\tiny $(11{,}\,14)$] (6) at (1.5*1,0) {};\node [enclosed, label=right:\tiny $(1{,}\,3)$] (7) at (0,-.75*1) {};}(1) -- (2);(2) -- (3);(1) -- (5);(5) -- (6);(4) -- (1);(4) -- (2);(4) -- (3);(4) -- (5);(4) -- (6);(1) -- (7);\) 
(3) edge[bend left = 60] (5);
(2) edge[bend left = 30] (5);
\(has this intersection graph.\) 
Finally suppose that \(\mathbb {G}\)  is an intersection graph extending \(\mathrm {II}\)  and containing the edge \(\lbrace v_2,v_6\rbrace \) . Then the vertices \(\lbrace v_2,v_6,v_5,v_4,v_3\rbrace \)  form a subgraph isomorphic to \(\mathrm {III}_5\)  labels occurring in the given order, so one of the edges \(\lbrace v_2,v_5\rbrace \) , \(\lbrace v_6,v_4\rbrace \) , or \(\lbrace v_6,v_3\rbrace \)  must also be in \(\mathbb {G}\) . Any graph containing the first two of these edges has already been explicitly covered, and any intersection graph with \(\lbrace v_3,v_6\rbrace \)  is covered by an argument symmetric to the argument for graphs containing \(\lbrace v_2,v_5\rbrace \) . Thus every such \(\mathbb {G}\)  already has an edge in our proposed necessary set.
This necessary set is of minimal cardinality because all necessary sets must contain all but one of the proposed edges
Lemma 8.14 The dotted edges in
\(\hbox{\begin{tikzpicture}[circle dotted/.style={dash pattern= on .05mm off 1mm, line cap = round, line width = 0.3mm}]{enclosed/.style={draw, circle, inner sep=0pt, minimum size=.1cm, fill=black}}\end{tikzpicture}\node [enclosed, label=left:$\beta $] (bl) at (-3*0.75,0) {};\node [enclosed, label=right:$\delta $] (br) at (3*0.75,0) {};\node [enclosed, label={[label distance=-2mm]135:$\gamma $}] (u) at (0,1*0.75) {};\node [enclosed, label=above:$\alpha $] (uu) at (0,2*0.75) {};\node [enclosed, label=below:$1$] (1) at (-2*0.75,0) {};\node [enclosed, label=below:$2$] (2) at (-1*0.75,0) {};\node [enclosed, label=below:$3$] (3) at (0,0) {};\node [enclosed, label=below:$m$] (n) at (2*0.75,0) {};}\) 
in 1,2,3,n
(u) – ();
(bl) – (1);
(n) – (br);
(uu) – (u);
[evaluate=as using +1] in 1,2
() – ();
[dashed] (3) – (n);
[circle dotted] (1) edge[bend right = 50] (n);
[circle dotted] (u) – (bl);
[circle dotted] (u) – (br);
[circle dotted] (uu) – (1);
[circle dotted] (uu) – (2);
[circle dotted] (uu) – (n);
[circle dotted] (uu) edge[bend left = 20] (3);
\(form a necessary set of minimal cardinality for \) 
IVm\( in \) L2\(.\)
As before, we start by identifying the set \(A=\lbrace \alpha ,\beta ,\delta \rbrace \)  as being asteroidal in \(\mathrm {IV}_m\) .
The edges \(\lbrace \beta ,\gamma \rbrace \) , \(\lbrace \gamma ,\delta \rbrace \) , and \(\lbrace \alpha ,i\rbrace \)  for each \(1\le i\le m\)  must be in every necessary set for \(\mathrm {IV}_m\)  as \(\mathrm {IV}_m\)  becomes an intersection graph as soon as any one of the above edges is added. Up to symmetry, representative examples of these intersection graphs are:
\(\hbox{\begin{tikzpicture}[circle dotted/.style={dash pattern= on .05mm off 1mm, line cap = round, line width = 0.3mm}]{enclosed/.style={draw, circle, inner sep=0pt, minimum size=.1cm, fill=black}}\end{tikzpicture}\node [enclosed, label=left:\tiny {$(3,4)$}] (bl) at (-1.5*0.75,0) {};\node [enclosed, label=right:\tiny {$(7,8)$}] (br) at (1.5*0.75,0) {};\node [enclosed, label={[label distance=-2mm, xshift=.3mm]45:\tiny {$(1,6)$}}] (u) at (0,1*0.75) {};\node [enclosed, label=above:\tiny {$(1,2)$}] (uu) at (0,2*0.75) {};\node [enclosed, label=below:\tiny {$(3,6)$}] (1) at (-.5*0.75,0) {};\node [enclosed, label=below:\tiny {$(5,8)$}] (2) at (.5*0.75,0) {};}\) 
in 1,2
(u) – ();
(bl) – (1);
(2) – (br);
(uu) – (u);
[evaluate=as using +1] in 1
() – ();
(u) edge (bl);
   
\(It remains to show that any intersection graph extending \) 
IVm\( and not containing any of the aforementioned edges must contain the edge \) {1,m}\( (and that such intersection graphs do exist).\) If \(\mathbb {G}\)  extends \(\mathrm {IV}_m\)  and \(\lbrace \alpha ,\beta \rbrace \)  is in \(\mathbb {G}\)  then \(\lbrace \alpha ,\beta ,1,\gamma \rbrace \)  forms a 4-cycle and so either \(\lbrace \alpha ,1\rbrace \)  is in \(\mathbb {G}\)  or \(\lbrace \beta ,\gamma \rbrace \)  is in \(\mathbb {G}\) . However, both of these options are already covered, so \(\lbrace \alpha ,\beta \rbrace \)  cannot be in a \(\subseteq \) -minimal necessary set. A symmetric argument gets the same result for the edge \(\lbrace \alpha ,\delta \rbrace \) .
Now, in order to avoid \(A\)  being asteroidal, an intersection graph extending \(\mathrm {IV}_m\)  and having none of the previously mentioned edges must have one of the edges \(\lbrace \beta ,\delta \rbrace \) , \(\lbrace \beta ,m\rbrace \) , or \(\lbrace \delta ,1\rbrace \) . If \(\lbrace \beta ,\delta \rbrace \)  is an edge of \(\mathbb {G}\)  then the vertices \(\lbrace \beta ,\delta ,m,\gamma ,1\rbrace \)  form a 5-cycle so one of the edges \(\lbrace 1,m\rbrace ,\lbrace \gamma ,\delta \rbrace ,\)  or \(\lbrace \gamma ,\beta \rbrace \)  must appear in \(\mathbb {G}\) , but we have already ruled out the latter two, so \(\lbrace 1,m\rbrace \)  must be in \(\mathbb {G}\) .
If \(\lbrace \beta ,m\rbrace \)  is in \(\mathbb {G}\)  then the vertices \(\lbrace \beta ,m,\gamma ,1\rbrace \)  form a 4-cycle and so either \(\lbrace \beta ,\gamma \rbrace \)  is in \(\mathbb {G}\)  or \(\lbrace 1,m\rbrace \)  is in \(\mathbb {G}\) . We already know that graphs with \(\lbrace \beta ,\gamma \rbrace \)  are covered, so we must have that \(\lbrace 1,m\rbrace \)  is in \(\mathbb {G}\) . A symmetric argument for \(\lbrace \delta ,1\rbrace \)  also shows that \(\lbrace 1,m\rbrace \)  must be an edge in \(\mathbb {G}\) .
The result now follows from the fact that the extension of \(\mathrm {IV}_m\)  with the vertices \(\lbrace \beta ,\delta \rbrace \cup \lbrace 1,\dots ,m\rbrace \)  inducing a complete subgraph and otherwise having only the edges from \(\mathrm {IV}_m\)  is an intersection graph. An example of intervals producing such a graph could be given by setting all of the vertices labelled \(1,\dots ,m\)  to the same non-empty interval and also identify the vertices labelled \(\beta \)  and \(\delta \) . These identifications lead to a quotient graph of the proposed graph that is isomorphic to a graph that is a single irreducible path, which was shown to be an intersection graph in Lemma REF .
Lemma 8.15 
The dotted edges in
\(\hbox{\begin{tikzpicture}[circle dotted/.style={line width = 0.3mm, dash pattern= on .05mm off 1mm, line cap = round}, scale=1.5]{enclosed/.style={draw, circle, inner sep=0pt, minimum size=.1cm, fill=black}}\end{tikzpicture}}\node [enclosed, label=above left:\) 
\(] (o1) at ({cos(deg(2*pi/3))*},{sin(deg(2*pi/3))*}) {};\node [enclosed, label=above right:\)\(] (o2) at ({cos(deg(pi/3))*},{sin(deg(pi/3))*}) {};\)enclosed, label=left:\(\alpha \) ] (u1) at (cos(deg(5*pi/6))*,sin(deg(5*pi/6))*) ;
enclosed, label=[yshift=-1.3mm]above:\(\beta \) ] (u2) at (cos(deg(pi/2))*,sin(deg(pi/2))*) ;
enclosed, label=right:\(\gamma \) ] (u3) at (cos(deg(/2))*, sin(deg(/2))*) ;
/in 1/1,2/2,3/3
enclosed, label=below:] () at ((-1)/3-,0) ;
enclosed, label=below:\(n\) ] (4) at (,0) ;
in o1,o2
in 1,2,3,4
() – ();

(o1) – (o2);
[evaluate=as using +1] in 1,2
() – ();
[dashed] (3) – (4);
(1) – (u1);
(o1) – (u1);
(o1) – (u2);
(o2) – (u2);
(o2) – (u3);
(4) – (u3);
in 1,2,3
[circle dotted] (u2) edge[bend left = 10] ();
[circle dotted] (u2) edge[bend right = 10] (4);
[circle dotted] (o1) edge[bend left = 80, looseness = 2.4] (u3);
[circle dotted] (o2) edge[bend right = 80, looseness = 2.4] (u1);
\(form the unique necessary set of minimal cardinality for \) 
Vn\( in \) L2\(.\)
We first note that the set \(A=\lbrace \alpha ,\beta ,\gamma \rbrace \)  is asteroidal in \(\mathrm {V}_n\) . We also note that if any one of the edges \(\lbrace \gamma ,\delta \rbrace \) , \(\lbrace \alpha ,\epsilon \rbrace \) , or \(\lbrace \beta ,i\rbrace \)  for some \(1\le i\le n\)  are added to \(\mathrm {V}_n\) , then the resulting graph is an intersection graph, and so every necessary set for \(\mathrm {V}_n\)  contains the edges \(\lbrace \alpha ,\epsilon \rbrace \) , \(\lbrace \gamma ,\delta \rbrace \) , and \(\lbrace \beta ,i\rbrace \)  for each \(1\le i\le n\) . Representative examples of such graphs are (up to symmetry):
\(\hbox{\begin{tikzpicture}[circle dotted/.style={line width = 0.3mm, dash pattern= on .05mm off 1mm, line cap = round}, scale=1.25]{enclosed/.style={draw, circle, inner sep=0pt, minimum size=.1cm, fill=black}}\end{tikzpicture}}\node [enclosed, label={[label distance=-1mm]above left:\tiny {(1,8)}}] (o1) at ({cos(deg(2*pi/3))*},{sin(deg(2*pi/3))*}) {};\node [enclosed, label={[label distance=-1mm]above right:\tiny {(1,9)}}] (o2) at ({cos(deg(pi/3))*},{sin(deg(pi/3))*}) {};\) 
enclosed, label=left:\({(3,7)}\) ] (u1) at (cos(deg(5*pi/6))*,sin(deg(5*pi/6))*) ;
enclosed, label=[label distance=-.5mm, yshift=-1.3mm]above left:\({(1,2)}\) ] (u2) at (cos(deg(pi/2))*,sin(deg(pi/2))*) ;
enclosed, label=right:\({(10,11)}\) ] (u3) at (cos(deg(pi/6))*, sin(deg(pi/6))*) ;
enclosed, label=below:\({(3,6)}\) ] (1) at (-,0) ;
enclosed, label=below:\({(5,9)}\) ] (2) at (0,0) ;
enclosed, label=below:\({(7,11)}\) ] (3) at (,0) ;
in o1,o2
in 1,2,3
() – ();

(o1) – (o2);
[evaluate=as using +1] in 1,2
() – ();
(1) – (u1);
(o1) – (u1);
(o1) – (u2);
(o2) – (u2);
(o2) – (u3);
(3) – (u3);
(o2) edge[bend right = 80, looseness = 2] (u1);
   [circle dotted/.style=line width = 0.3mm, dash pattern= on .05mm off 1mm, line cap = round, scale=1.25]
enclosed/.style=draw, circle, inner sep=0pt, minimum size=.1cm, fill=black


enclosed, label=[label distance=-1mm]above left:\({(1,10)}\)] (o1) at (cos(deg(2*pi/3))*1,sin(deg(2*pi/3))*1) ;
enclosed, label=[label distance=-1mm]above right:\({(3,12)}\)] (o2) at (cos(deg(pi/3))*1,sin(deg(pi/3))*1) ;
enclosed, label=left:\({(1,2)}\) ] (u1) at (cos(deg(5*pi/6))*1.5*1,sin(deg(5*pi/6))*1.5*1) ;
enclosed, label=[yshift=-.5mm]above:\({(6,7)}\) ] (u2) at (cos(deg(pi/2))*1.5*1,sin(deg(pi/2))*1.5*1) ;
enclosed, label=right:\({(11,12)}\) ] (u3) at (cos(deg(pi/6))*1.5*1, sin(deg(pi/6))*1.5*1) ;
enclosed, label=below:\({(3,5)}\) ] (1) at (-1,0) ;
enclosed, label=below:\({(4,9)}\) ] (2) at (0,0) ;
enclosed, label=below:\({(8,10)}\) ] (3) at (1,0) ;
in o1,o2
in 1,2,3
() – ();

(o1) – (o2);
[evaluate=as using +1] in 1,2
() – ();
(1) – (u1);
(o1) – (u1);
(o1) – (u2);
(o2) – (u2);
(o2) – (u3);
(3) – (u3);
(u2) – (2);

\(\) 
Suppose that \(\mathbb {G}\)  is an intersection graph extending \(\mathrm {V}_n\)  and containing the edge \(\lbrace \alpha ,\beta \rbrace \) . Then the vertices \(\lbrace \alpha ,\beta ,\epsilon ,1\rbrace \)  form a 4-cycle, and so one of the edges \(\lbrace \beta ,1\rbrace \)  or \(\lbrace \alpha ,\epsilon \rbrace \)  must be contained in \(\mathbb {G}\)  as well. However, we already know that both of these edges must be in the necessary set.
If \(\mathbb {G}\)  contains the edge \(\lbrace \alpha ,\gamma \rbrace \)  then the vertices \(\lbrace \alpha ,\gamma ,\epsilon ,\delta \rbrace \)  form a 4-cycle, so one of the edges \(\lbrace \alpha ,\epsilon \rbrace \)  or \(\lbrace \gamma ,\delta \rbrace \)  must be in \(\mathbb {G}\) . Again, we already know that both of these edges must be in every necessary set.
At this point, no other edges can prevent \(A\)  from being asteroidal in an extension, so we have covered all the required cases.
Now that we have computed the minimal necessary sets for each of the minimal graphs that cannot appear as induced subgraphs of interval intersection graphs, we can state a theorem for \(\mathrm {SOP}\)  that is an analogue of Theorem REF .
Theorem 8.16 Let \( be a regular ultrafilter on the infinite cardinal \)\(. The following are equivalent:\begin{enumerate}\item  is good.\item  saturates some theory with \mathrm {SOP}.\item If (\mathbb {G}_\alpha )_{\alpha <\lambda } is a sequence of finite graphs such that \mathrm {I},\mathrm {II},\mathrm {III}_\ell ,\mathrm {IV}_m,\mathrm {V}_n\nleq \mathbb {G}_\alpha  for each \alpha  and \ell \ge 4,m\ge 2, and n\ge 1, then every complete \mathbb {H}\subseteq \mathbb {G}_\alpha ^:\mathbb {G} with |\mathbb {H}|\le \lambda  has some internal complete subgraph of \mathbb {G} containing it.\item Every graph-like function f:\mathcal {P}_\omega (\lambda )\rightarrow  that satisfies the conditions given by specializing the subset relation~(\ref {necdisteqn}) to the necessary sets found for \mathbb {H}=\mathrm {I},\mathrm {II},\mathrm {III}_\ell ,\mathrm {IV}_m,\mathrm {V}_n in Lemmas~\ref {IIInecsets}--\ref {Vnecsets} has a multiplicative refinement.\end{enumerate}\)
\((1)\)\(\iff \)\((2)\) : Follows from e.g. [1]}.
\((2)\)\(\iff \)\((3)\) : A special case of Theorem REF .
\((2)\)\(\iff \)\((4)\) : Follows from Theorem REF  and Lemmas REF –REF .

\(\mathrm {SOP}_n\)  for \(n>2\)
In this section, our goal is to show that graph-like distributions corresponding to types whose realizations would fill a cut in an ultrapower of an infinite linear order (that is, types that characteristically appear in theories with \(\mathrm {SOP}\) ) also appear as graph-like distributions for types that appear in theories with \(\mathrm {SOP}_3\) , regardless of whether they also have \(\mathrm {SOP}\) . In essence this will show that distributions in theories with \(\mathrm {SOP}_n\)  for \(n\ge 3\)  are not only complicated enough to guarantee that the theory is Keisler maximal but are complicated enough to mimic the distributions of theories where models contain infinite linear orders. This argument is a close cousin to the argument made in [1]} that theories with \(\mathrm {SOP}_3\)  are Keisler maximal, but is more elementary.
Theorem 8.17 
Suppose that \( is a regular ultrafilter on the infinite cardinal \)\(, \) L=(L,<)\( is a linear order, \) (x;y,z)\( is the formula \) y<x<z\(, and \) p(x)={(x;a,b):<}\( is a type of \) L. Then, for every distribution \(f\)  of \(p(\bar{x})\)  and graph-like distribution \(\hat{f}\)  extending \(f\)  and every complete first-order theory \(T\)  with \(\mathrm {SOP}_3\) , there is a model \(\mathbb {M}\vDash T\)  and a graph-like type \(q(\bar{y})\)  of \(\mathbb {M}^ with a distribution \) f'\( satisfying \) f=f'\( (up to bijection between \) p(x)\( and \) q(y)\().\)
Fix representations of \(a_\beta ,b_\beta \)  and a distribution \(f\)  of \(p(\bar{x})\)  given these representations. Since \(p\)  is graph-like under any choice of representations in \(L\) , there is a graph-like distribution \(\hat{f}\)  extending \(f\) . Let the distribution graph sequence of \(\hat{f}\)  be \((\mathbb {G}_\alpha )_{\alpha <\lambda }\)  where each \(\mathbb {G}_\alpha \)  is a finite intersection graph (see Lemma REF ). Let \(I(\lambda )\)  be the collection of open intervals \(I\)  in \(\lambda \)  with the property that \(\min (I)\)  is a successor ordinal. For each \(\alpha <\lambda \)  let \(i_\alpha :\lambda \rightarrow I(\lambda )\)  be a function such that \(i_\alpha \text{\,}\mathord {\upharpoonright }\text{\,}_{\mathbb {G}_\alpha }\)  is a bijection and \(i_\alpha (\beta )\)  and \(i_\alpha (\gamma )\)  intersect if and only if \(\beta \)  and \(\gamma \)  are neighbors in \(\mathbb {G}_\alpha \) . Furthermore, we require that no two intervals in the image of \(i_\alpha \)  have endpoints in common. Let the functions \(\ell ,r:I(\lambda )\rightarrow \lambda \)  be the functions defined by
\(\ell (I)=\inf (I)\;\text{ and }\;r(I)=\sup (I).\) 
The function \(\ell (I)\)  is well-defined by the requirement that \(\min (I)\)  be a successor ordinal.
By [1]}, \(T\)  has \(\mathrm {SOP}_3\)  if and only if there is a model \(\mathbb {M}\vDash T\)  containing an indiscernible sequence \((\bar{a}_i)_{i\in \omega }\)  and formulas \(\theta (\bar{x},\bar{y})\)  and \(\eta (\bar{x},\bar{y})\)  such that

the set \(\lbrace \theta (\bar{x},\bar{y}),\eta (\bar{x},\bar{y})\rbrace \)  is contradictory,

for some sequence \((b_j)_{j\in \omega }\)  we have
\(i\le j\Rightarrow \theta (\bar{b}_j,\bar{a}_i)\;\,\text{ and }\;\,i>j\Rightarrow \eta (\bar{b}_j,\bar{a}_i)\) 

for \(i<j\) , the set \(\lbrace \theta (\bar{x},\bar{a}_j),\eta (\bar{x},\bar{a}_i)\rbrace \)  is contradictory.

Using compactness, we may extend the sequences \(\bar{a}\)  and \(\bar{b}\)  to sequences indexed by \(\lambda \) . Let \((\bar{a}_i)_{i\in \lambda }\) , \((\bar{b}_j)_{j\in \lambda }\) , \(\theta (\bar{x},\bar{y})\) , and \(\eta (\bar{x},\bar{y})\)  be as above. We then define
\(\psi (\bar{x};\bar{y},\bar{z})\equiv \theta (\bar{x},\bar{y})\wedge \eta (\bar{x},\bar{z}).\) 
Furthermore, define \((\bar{c}_\beta )_{\beta \in \lambda }\)  and \((\bar{d}_\beta )_{\beta \in \lambda }\)  in \(\mathbb {M}^ by the representations\)\(\bar{c}_\beta [\alpha ]=\bar{a}_{\ell (i_{\alpha }(\beta ))}\;\text{ and }\;\bar{d}_\beta [\alpha ]=\bar{a}_{r(i_{\alpha }(\beta ))}.\)\(We claim that the set of formula\)\(q(\bar{x})=\lbrace \psi (\bar{x};\bar{c}_\beta ,\bar{d}_\beta ):\beta <\lambda \rbrace \)\(is a graph-like type with distribution \) f\(.\) In order to check that \(q(\bar{x})\)  is graph-like, suppose that \(\Delta \in \mathcal {P}_\omega (\lambda )\)  is such that \(|\Delta |\ge 2\) . We wish to show that
\(L_q(\Delta )=\bigcap _{\Phi \in [\Delta ]^2}L_q(\Phi ),\) 
where \(L_q\)  is the Łoś map for \(q(\bar{x})\) . In order to do this, we will instead show that
\(L_q(\Delta )=\Big \lbrace \alpha \in \lambda :\bigcap i_\alpha [\Delta ]\ne \emptyset \Big \rbrace ,\) 
which will be enough because of the fact that an intersection of open intervals is non-empty if and only if the intersection of every pair of intervals in the collection is non-empty. Suppose that \(j\in \bigcap i_\alpha [\Delta ]\) . Then we have that \(\mathbb {M}\vDash \psi (\bar{b}_j;\bar{c}_\beta [\alpha ],\bar{d}_\beta [\alpha ])\)  for each \(\beta \in \Delta \)  because \(\ell (i_\alpha (\beta ))<j<r(i_\alpha (\beta ))\)  by the definition of \(j\) . Now suppose that \(\bigcap i_\alpha [\Delta ]=\emptyset \) . Then there is some distinct pair \(\beta ,\gamma \in \Delta \)  such that \(r(i_\alpha (\beta ))\le \ell (i_\alpha (\gamma ))\) . Furthermore, because the intervals in the image of \(i_\alpha \)  cannot repeat endpoints, this inequality is strict. In particular, this means that the formula
\(\psi (\bar{x};\bar{c}_\beta [\alpha ],\bar{d}_\beta [\alpha ])\wedge \psi (\bar{x};\bar{c}_\gamma [\alpha ],\bar{d}_\gamma [\alpha ])\) 
cannot be satisfied in \(\mathbb {M}\) .
We check that \(\hat{f}\)  is a distribution of the type \(q(\bar{x})\)  with the given representations. By the fact that \(q(\bar{x})\)  and \(\hat{f}\)  are graph-like, it will be enough to check that \({\hat{f}(\Delta )\subseteq L(\Delta )}\)  for all \(\Delta \in \mathcal {P}_\omega (\lambda )\)  with \({|\Delta |\le 2}\) . However, this follows immediately from Equation (REF ) and the fact that \(\hat{f}\)  is a distribution for \(p(\bar{x})\) .
Corollary 8.18 Theorem REF  is true whenever \(T\)  is replaced with a theory with \(\mathrm {SOP}_n\)  for \(n>3\) .

By [1]}, \(\mathrm {SOP}_n\Rightarrow \mathrm {SOP}_3\)  whenever \(n\ge 3\) .
Given the difficulty in proving that theories with \(\mathrm {SOP}_2\)  are maximal in Keisler's order, we believe that the above theorem is not true for \(T\)  with \(\mathrm {SOP}_2\) . We note that if this conjecture is true, then \(\mathrm {SOP}_3\)  and \(\mathrm {SOP}_2\)  must be different on the level of theories as has been previously conjectured by Shelah.
Acknowledgements
Much thanks goes to Ágnes Szendrei for boundless advice given throughout the writing process and for suggesting looking at distributions related to \(\mathrm {SOP}_n\)  for \(n>2\) . This material is based upon work supported by the National Science Foundation grant no. DMS1500254.
