Abstract Abstract. We classify graphs that are 0, 1, or 2 edges short of being complete partite graphs with respect to intrinsic linking and intrinsic knotting. In addition, we classify intrinsic knotting of graphs on 8 vertices. For graphs in these families, we verify a conjecture presented in Adams' The Knot Book: If a vertex is removed from an intrinsically knotted graph, one obtains an intrinsically linked graph. Abstract We say that a graph is intrinsically knotted (respectively, linked) if every tame embedding of the graph in R 3 contains a non-trivially knotted cycle (respectively, pair of non-trivially linked cycles). Robertson, Seymour, and Thomas [9] demonstrated that intrinsic linking is determined by the seven Petersen graphs. A graph is intrinsically linked if and only if it is or contains one of the seven as a minor. They also showed [8] that a similar, finite list of graphs exists for the intrinsic knotting property. However, determining this list remains difficult. Abstract It is known [2, 4, 6, 7] that K 7 and K 3,3,1,1 along with any graph obtained from these two by triangle-Y exchanges is minor minimal with respect to intrinsic knotting. Recently Foisy [5] has added a new minor minimal graph to the list. Foisy's example is particularly interesting from our perspective as it provides a counterexample to the "unsolved question" posed in Adams' [1] book: Is it true that if G [a graph] is intrinsically knotted and any one vertex and the edges coming into it are removed, the remaining graph is intrinsically linked? Abstract While Adams' conjecture is not true in general, it does appear to hold for a wide array of graphs, particularly graphs that are "almost" complete. We will say a graph is k-deficient if it is a complete or complete partite graph with k edges removed. In the current article we verify Adams' conjecture for 0-, 1-, and 2-deficient graphs. This can be seen as the first few steps in a project to find a counterexample to Adams' conjecture of minimum deficiency. However, as Foisy's counterexample is 13-deficient, there is a long way to go in this program. Abstract More promising is the search for a counterexample on a minimum number of vertices. Since K 7 is a minor minimal intrinsically knotted graph, it is the only graph on 7 or fewer vertices that is intrinsically knotted. In the current paper, we show that there are twenty intrinsically knotted graphs on 8 vertices. These all satisfy Adams' conjecture, so a minimal counterexample to the conjecture must have between 9 vertices and the 13 of Foisy's graph. Abstract In classifying intrinsic knotting of various families, we have made use of the known minor minimal examples derived from K 7 and K 3,3,1,1 by triangle-Y exchanges. In particular, we include here a table of the 25 graphs obtained from K 3,3,1,1 ([6] includes the table built on K 7 ). Note that there are no new examples of minor minimal intrinsically knotted graphs to be found among 0-, 1-, and 2-deficient graphs and graphs on 8 vertices. Abstract The paper is organized as follows. Following this introduction, Section 2 presents some fundamental lemmas and the table of graphs obtained from K 3,3,1,1 by triangle-Y exchanges. In Sections 3,4, and 5 we investigate 0-, 1-, and 2-deficient graphs respectively. In each case we classify the graphs with respect to intrinsic knotting and linking and demonstrate that they satisfy Adams' conjecture. In Section 6 we classify intrinsically knotted graphs on 8 vertices and verify that they too satisfy Adams' conjecture. We complete the paper by formulating the analogue to a question Sachs asked about intrinsic linking. We show that if 5 ≤ n ≤ 8, a graph on n vertices that is not intrinsically knotted will have at most 5n − 15 edges and ask if this is true more generally: Question: Is there a graph on n vertices that is not intrinsically knotted and has more than 5n − 15 edges? 2. Lemmas and graphs derived from K 3,3,1,1 Abstract In this section we present some useful lemmas as well as a table of graphs derived from K 3,3,1,1 by triangle-Y exchanges. Let us begin with some notation. We will use K a1,a2,...,ap to denote a complete partite graph with p parts containing respectively a 1 , a 2 , . . . , a p vertices. Permuting the a i results in the same graph. We will usually write the parts in descending order: a 1 ≥ a 2 ≥ . . . ≥ a p . The complete graph on n vertices is denoted K n . Abstract Recall that a minor of a graph G is the resultant graph after performing a finite number of vertex or edge deletions and edge contractions on G. An example of an edge contraction is shown in figure 1 (moving from left to right in the figure). Moving from right to left in the figure is known as splitting a vertex. We say a graph G is minor minimal with respect to a property if G exhibits the property but no minor of G does. For example, the seven Petersen graphs are the only graphs minor minimal with respect to intrinsic linking. An intrinsically linked graph must either be a Petersen graph or contain one as a minor. Abstract The analogous list of graphs for intrinsic knotting is incomplete at this time. We do know that the list is finite [8] and if G is in the list, so is any graph obtained from G by triangle-Y exchanges [7] . To perform a triangle-Y exchange on a graph, find 3 vertices that are all connected to one another, delete the three edges between them, and replace with a single vertex connected to all 3 vertices of the triangle. Kohara and Suzuki [6] have provided a list of the 13 graphs arising from K 7 by triangle-Y exchanges. They state that these graphs are minor-minimal with respect to intrinsic knotting and remark that there are 25 graphs that can be constructed from K 3,3,1,1 by triangle-Y exchanges. We present these graphs in figure 2. Since Foisy [4] showed that K 3,3,1,1 is intrinsically linked it follows [6] that all 26 graphs in the figure are minor minimal with respect to intrinsic knotting. Abstract The graphs in figure 2 are organized into rows having equal numbers of vertices. The arrows indicate that a triangle-Y exchange has occurred. A dashed arrow means that the triangle-Y exchange will result in a different projection of the graph than that shown in the figure. Note that graphs B 13 , C 13 , and A 14 contain no triangles. Most graphs in the figure can be shown to be different from the others by examining the set of vertex degrees. The exceptions are the pairs A 11 and B 11 , E 11 and G 11 , A 12 and B 12 , and A 13 and B 13 . Abstract We can distinguish the members of these pairs as follows. B 11 contains a triangle of degree 5 vertices while A 11 does not. G 11 contains a degree 3 vertex that is connected only to degree 4 vertices; E 11 contains no such degree 3 vertex. A 12 contains a 5,5,4 triangle. The two degree 5 vertices in B 12 are connected to no common degree 4 vertex so such a triangle is not possible. A 13 contains a triangle; no triangles exist in B 13 Abstract These lists of known intrinsically linked or knotted graphs will be one of the two main techniques used in our classifications. If we know that a graph G contains a linked (knotted) minor, then G must also be linked (knotted). Conversely, if we can realize G as a minor of an unlinked (unknotted) graph, we deduce that G must also be unlinked (unknotted). A useful lemma in this regard shows how we can combine parts of a k-deficient graph. Proof: Combining the n 1 and n 2 parts only involves removing edges between vertices in the n 1 part and the n 2 part. Recall that with complete partite graphs, the ordering of the subscripts is not important, so this lemma implies that we can combine any 2 parts to get a minor of the original graph. Now, suppose we have a complete partite graph with k edges removed and we combine two parts. The result would be a complete partite graph with 1 fewer part and at most k edges removed. Abstract Furthermore, if there are m edges missing between parts n 1 and n 2 , we can see that K n1+n2,n3,...,n k − (k − m) edges is a minor of K n1,n2,...,n k − k edges. Abstract The other main technique we will use in our classifications is based on a lemma for intrinsic linking due to Sachs [10] and an analogous result for intrinsic knotting proved by Fleming [3] . Let G + H denote the suspension of graphs G and H, i.e., the graph obtained by taking the union of G and H and adding an edge between each vertex of G and each vertex of H. Abstract Lemma 2 ([10] ). The graph G + K 1 is intrinsically linked if and only if G is non-planar Corollary 3. If a vertex is deleted from a graph H and the result is a planar graph, then H is not intrinsically linked. Abstract If the deleted vertex was connected to every other vertex, then by lemma 2, H is not intrinsically linked. If the deleted vertex was not connected to every other vertex, then H is a minor of a graph that is not intrinsically linked by lemma 2. Abstract ). The graph G + K 2 is intrinsically knotted if and only if G is non-planar Corollary 5. If two vertices are deleted from a graph H and the result is a planar graph, then H is not intrinsically knotted. Abstract Note that if we use lemma 4 to argue that a graph H = G + K 2 is intrinsically linked, then, G must contain K 5 or K 3,3 as a minor. It follows that H contains K 7 or K 3,3,1,1 as a minor. As our only other technique relies on the family of graphs obtained by triangle-Y exchanges from K 7 and K 3,3,1,1 , our methods cannot possibly add to the list of known minor-minimal graphs. In other words, every intrinsically knotted graph that is 0-, 1-, or 2-deficient or a graph on 8 vertices necessarily is or has as a minor one of the minor minimal graphs obtained from K 7 or K 3,3,1,1 by triangle-Y exchanges. Abstract In this section we classify complete graphs and complete partite graphs with respect to intrinsic linking. The classification of these graphs with respect to intrinsic knotting is due to Fleming [3]. We use these classifications to prove that Adams' conjecture holds for this class of graphs. Abstract Theorem 6. The complete k-partite graphs are classified with respect to intrinsic linking according to Table 1 . k 1 2 3 4 5 ≥ 6 linked 6 4,4 3,3,1 2,2,2,2 2,2,1,1,1 All 4,2,2 3,2,1,1 3,1,1,1,1 not linked 5 n,3 3,2,2 2,2,2,1 2,1,1,1,1 None n,2,1 n,1,1,1 Table 1 . Intrinsic linking of complete k-partite graphs. Abstract Remark: The n in the notation K n,3 indicates that the property holds for any number of vertices in that part, i.e., none of the graphs K 1,3 , K 2,3 , K 3,3 , . . . are intrinsically linked. For each k, the table includes minimal examples of intrinsically linked complete k-partite graphs and maximal graphs which are not intrinsically linked. For example, any complete 2-partite graph which contains K 4,4 as a minor is intrinsically linked. On the other hand, any complete 2-partite graph which is a minor of a K n,3 is not linked. Thus, K l,m is intrinsically linked if and only if l ≥ 4 and m ≥ 4. Abstract Proof: Let us demonstrate that the graphs labeled "linked" in Table 1 are in fact intrinsically linked. Abstract Conway and Gordon [2] proved that K 6 is linked. Any k-partite graph with k ≥ 6 contains K 6 = K 1,1,1,1,1,1 as a minor and is therefore linked. For the remaining k, we appeal to work of Robertson, Seymour, and Thomas [9] who showed that a graph is intrinsically linked if and only if it is or contains as a minor one of the seven graphs in the Petersen family. In particular, K 4,4 with one edge removed and K 3,3,1 are both in this family. By combining parts, we see that, for 2 ≤ k ≤ 5, one of these two is a minor of each of the "linked" graphs in Table 1 . Abstract For each of the "not linked" examples in Table 1 which involve a part with a single vertex, the corresponding graph obtained by removing that vertex is planar. Therefore, by lemma 4, these graphs are not intrinsically linked. Abstract Since a cycle requires at least three vertices, K 5 has no disjoint pair of cycles and is therefore not linked. The remaining "not linked" graphs in Table 1 , K n,3 and K 3,2,2 , are, respectively, minors of the unlinked graphs K n,2,1 and K 2,2,2,1 . Abstract Theorem 7. If G is an intrinsically knotted complete partite graph, and any one vertex and the edges coming into it are removed, the remaining graph is intrinsically linked. Abstract Proof: For the reader's convenience, we reproduce Fleming's [3] classification of knotted partite graphs as Table 2 below. k 1 2 3 4 5 6 ≥ 7 knotted 7 5,5 3,3,3 3,2,2,2 2,2,2,2,1 2,2,1,1,1,1 All 4,3,2 4,2,2,1 3,2,2,1,1 3,1,1,1,1,1 4,4,1 3,3,2,1 3,2,1,1,1 3,3,1,1 not knotted 6 4,4 3,3,2 2,2,2,2 2,2,2,1,1 2,1,1,1,1,1 None n,2,2 4,2,1,1 2,2,1,1,1 n,3,1 3,2,2,1 n,1,1,1,1 n,2,1,1 n,1,1,1 Table 2 . Intrinsic knotting of k-partite graphs. Abstract It suffices to verify the theorem for minimal examples of knotted k-partite graphs, k = 1, 2, 3, . . .. k = 1: A complete graph K n is intrinsically knotted iff n ≥ 7. Removing a vertex from K 7 produces K 6 which is intrinsically linked. k = 2: K 5,5 is the minor-minimal knotted 2-partite graph. (Note that K n,4 is not intrinsically knotted for n ≥ 5. This is implicit in [3] .) Removing a vertex from K 5,5 yields K 5,4 which is intrinsically linked. k = 3: There are three minor-minimal knotted 3-partite graphs: K 3,3,3 , K 4,3,2 , and K 4,4,1 . Removing a vertex from one of these results in one of the following linked graphs: K 4,4 , K 3,3,2 , K 4,2,2 , or K 4,3,1 . k = 4: Here the minimal knotted graphs are K 3,2,2,2 , K 3,3,1,1 and K 4,2,2,1 (The graph K 3,3,2,1 listed by Fleming [3] is redundant as it includes K 3,3,1,1 as a minor.) Removing a vertex from any of these we obtain one of the linked graphs K 3,3,1 , K 4,2,2 , K 2,2,2,2 , K 3,2,1,1 , K 3,2,2,1 , or K 4,2,1,1 . Abstract In this case we must check the knotted graphs K 2,2,2,2,1 and K 3,2,1,1,1 . (Fleming's [3] K 3,2,2,1,1 is redundant.) Taking a vertex from either of these results in a linked graph: K 2,2,2,2 , K 3,2,1,1 , K 2,2,1,1,1 , K 2,2,2,1,1 , or K 3,1,1,1,1 . k = 6: Here there are two knotted graphs: K 2,2,1,1,1,1 and K 3,1,1,1,1,1 . After a vertex is deleted, we're left with one of these linked graphs: K 2,2,1,1,1 , K 3,1,1,1,1 , or K 2,1,1,1,1,1 . k ≥ 7: All such graphs are intrinsically knotted. On removing a vertex, we obtain an l-partite graph where l ≥ 6. All such graphs are intrinsically linked. Abstract In this section we classify 1-deficient graphs with respect to intrinsic linking and knotting. We use the classification to prove Adams' conjecture for this family of graphs. Notation: Often, we will have to talk about a particular vertex or part. We will refer to parts alphabetically with capital letters and vertices of those parts with lower case letters. For example, in K 4,3,1 , we will call the part with 4 vertices part A, the part with 3 vertices part B, and the part with 1 vertex part C. An edge between parts A and C would be labeled (a,c). Abstract Theorem 8. The 1-deficient graphs are classified with respect to intrinsic linking according to Table 3 . Abstract 7-e 4,4-e 4,3,1-e 2,2,2,2-e 2,2,1,1,1-(b,c) 2,1,1,1,1,1-e All 3,3,2-e 3,2,1,1-(b,c) 3,1,1,1,1-(b,c) 4,2,2-e 4,2,1,1-e 4,1,1,1,1-e 3,3,1,1-e 3,2,1,1,1-e 3,2,2,1-e 2,2,2,1,1-e not linked 6-e n,3-e 3,2,2-e 2,2,2,1-e 2,2,1,1,1-(a,b) 1,1,1,1,1,1-e None n,2,1-e n,1,1,1-e 2,2,1,1,1-(c,d) 3,3,1-e 3,2,1,1-(a,b) 3,1,1,1,1-(a,b) 3,2,1,1-(a,c) 2,1,1,1,1-e 3,2,1,1-(c,d) Table 3 . Intrinsic Linking of 1 Deficient Graphs. Abstract Note that most of these graphs have different types of edges. For some graphs, removal of one edge (e.g., (a,b)) will result in a non-linked graph while the removal of a different edge (e.g., (b,c)) will result in a linked graph. However, in many cases, removal of any edge will result in the same categorization. In such cases we simply write "-e". For example, no matter which edge we remove from K 3,2,2 , we will obtain a graph that is not intrinsically linked. Abstract Linked: Abstract Let us demonstrate that the graphs labeled "linked" in Table 3 are in fact intrinsically linked. K 7 -e has K 6 as a minor. To see this, simply delete a vertex that the removed edge was attached to. Any 1-deficient graph with 7 or more parts will contain K 7 -e (or, equivalently, K 1,1,1,1,1,1,1 -e). Abstract Recall that K 4,4 -e is a Petersen graph, and therefore is intrinsically linked. Note that by lemma 1, K 4,3,1 -e, K 4,2,2 -e, K 2,2,2,2 -e, K 4,2,1,1 -e, K 3,3,1,1 -e, K 3,2,2,1 -e, K 4,1,1,1,1 -e, K 3,2,1,1,1 -e, and K 2,2,2,1,1 -e all contain K 4,4 -e as a minor, and are therefore all intrinsically linked. K 3,3,2 -e has 2 cases: K 3,3,2 -(a,b) and K 3,3,2 -(b,c); both are intrinsically linked. For K 3,3,2 -(a,b), contract the edge between vertex b and c to get K 3,2,1,1 . For K 3,3,2 -(b,c), simply delete vertex c for K 3,3,1 . So in either case, K 3,3,2 -e is intrinsically linked. Abstract By lemma 1, K 3,2,1,1 -(b,c), K 2,2,1,1,1 -(b,c), and K 3,1,1,1,1 -(b,c) all contain K 3,3,1 as a minor and are therefore intrinsically linked. Abstract There are 2 cases of K 2,1,1,1,1,1 -e: K 2,1,1,1,1,1 -(a,b) and K 2,1,1,1,1,1 -(b,c). For K 2,1,1,1,1,1 -(a,b), simply delete a to get K 6 , and notice that K 2,1,1,1,1,1 -(b,c) is equivalent to K 2,2,1,1,1 . So both cases are intrinsically linked. Abstract Not Linked: Abstract K 6 (or K 1,1,1,1,1,1 ) and K 3,3,1 are Petersen graphs and therefore minor minimal with respect to intrinsic linking [9], so K 6 -e and K 3,3,1 -e are not intrinsically linked by definition of minor minimal. Abstract K n,3 -e, K 3,2,2 -e, K n,2,1 -e, K 2,2,2,1 -e, K n,1,1,1 -e, and K 2,1,1,1,1 -e are all not intrinsically linked before the edge is removed; so, naturally, we can remove an edge and still have a non-intrinsically linked graph. Abstract ) is equivalent to K 3,2,2 which is not intrinsically linked. The remaining graphs all have a vertex that is connected to every other vertex, and the removal of that vertex results in a planar graph. So, by lemma 4, none are intrinsically linked. k 1 2 3 4 5 6 7 ≥ 8 knotted 8-e 5,5-e 3,3,3-e 3,2,2,2-e 2,2,2,2,1-e 2,2,1,1,1,1-(b,c) 2,1,1,1,1,1,1-e All 4,3,2-e 4,2,2,1-e 3,2,1,1,1-(b,c) 3,1,1,1,1,1-(b,c) 4,4,1-e 3,3,2,1-e 4,2,1,1,1-e 3,2,1,1,1,1-e 4,3,1,1-e 3,3,1,1,1-e 2,2,2,1,1,1-e 3,2,2,1,1-e 4,1,1,1,1,1-e not knotted 7-e n,4-e 3,3,2-e 3,3,1,1-e 3,2,1,1,1-(c,d) 2,2,1,1,1,1-(a,b) 1,1,1,1,1,1,1-e None n,2,2-e 2,2,2,2-e 3,2,1,1,1-(a,b) 2,2,1,1,1,1-(c,d) n,3,1-e 3,2,2,1-e 3,2,1,1,1-(a,c) 3,1,1,1,1,1-(a,b) n,2,1,1-e 2,2,2,1,1-e 2,1,1,1,1,1-e n,1,1,1,1-e Table 4 . Intrinsic knotting of 1 deficient graphs. Abstract Theorem 9. The 1-deficient graphs are classified with respect to intrinsic knotting according to Table 4 . Abstract Knotted: Abstract Let us demonstrate that the graphs labeled "knotted" in Table 4 are in fact intrinsically knotted. K 8 -e is has K 7 as a minor; to see this, simply delete a vertex that the removed edge was connected to. All 1-deficient graphs with 8 or more parts will contain K 1,1,1,1,1,1,1,1 -e = K 8 -e. Abstract K 5,5 − e is intrinsically knotted as proved in [11] . It is also helpful to see that it is an expansion of H 9 from [6], a fact pointed out in [4] . Abstract K 3,3,3 − e is intrinsically knotted. As shown in figure 3 , several edges are added to H 9 to get K 3,3,3 . H 9 was shown to be intrinsically knotted in [6] . So, if we simply add 1 fewer of those edges, we arrive at K 3,3,3 − e and our graph is still intrinsically knotted. Notice that any two edges in K 3,3,3 are equivalent to one another. By lemma 1, K 3,3,2,1 -e, K 3,3,1,1,1 -e, K 3,2,2,1,1 -e, K 3,2,1,1,1,1 -e, and K 2,2,2,1,1,1 -e all have K 3,3,3 -e as a minor, and are therefore all intrinsically knotted. K 4,3,2 − e is intrinsically knotted, there are 3 cases. Case 1: K 4,3,2 − (a, b). K 4,3,2 is intrinsically knotted as it contains K 3,3,1,1 as a minor (see figure 4) . Notice that if we add one fewer edge, we get K 4,3,2 − (a, b). , we see that K 4,3,2 − (b, c) contains H 9 as a minor; therefore it is intrinsically knotted. Abstract Case 3: K 4,3,2 − (a, c). The same as case 2, except we leave out edge (a ′ ,c ′ ). By lemma 1, K 3,2,2,2 -e, K 4,2,2,1 -e, K 4,3,1,1 -e, K 2,2,2,2,1 -e, K 4,2,1,1,1 -e, and K 4,1,1,1,1,1 -e all contain K 4,3,2 -e as a minor, and are therefore intrinsically knotted. Abstract K 4,4,1 − e is intrinsically knotted; there are 2 cases: K 4,4,1 − (a, b) and K 4,4,1 − (a, c). Abstract As shown in figure 6 , K 4,4,1 contains H 9 as a minor. If we refrain from adding either (a Abstract , we can see that both cases of K 4,4,1 -e have H 9 as a minor, and are therefore intrinsically knotted. Abstract By (the proof of) lemma 1, if we combine the parts of a missing edge of a 1-deficient graph, we will get a complete graph. If we combine parts B and C of K 3,2,1,1,1 -(b,c), K 2,2,1,1,1,1 -(b,c), or K 3,1,1,1,1,1 -(b,c), we will get K 3,3,1,1 or K 3,2,1,1,1 . So these three graphs are intrinsically knotted. Abstract K 2,1,1,1,1,1,1 -e has 2 cases: K 2,1,1,1,1,1,1 -(a,b) and K 2,1,1,1,1,1,1 -(b,c). For K 2,1,1,1,1,1,1 -(a,b), simply delete vertex a to get K 7 . K 2,1,1,1,1,1,1 -(b,c) is equivalent to K 2,2,1,1,1,1 . So both cases are intrinsically knotted. Abstract INTRINSIC KNOTTING AND LINKING OF ALMOST COMPLETE PARTITE GRAPHS 9 Figure 5 . H 9 is a Minor of K 4,3,2 Figure 6 . H 9 is a Minor of K 4,4,1 K 7 was shown to be minor minimally intrinsically knotted in [2] and K 3,3,1,1 was shown to be minor minimally intrinsically knotted in [4], so K 7 -e (or K 1,1,1,1,1,1,1 -e) and K 3,3,1,1 -e are not intrinsically knotted. Abstract In Fleming's paper [3], he showed that K 4,4 is not intrinsically knotted. In fact, his proof really showed that K n,4 is not intrinsically knotted, so, naturally, K n,4 -e is not intrinsically knotted either. Similarly, K 3,3,2 -e, K n,2,2 -e, K n,3,1 -e, K 2,2,2,2 -e, K 3,2,2,1 -e, K n,2,1,1 -e, K 2,2,2,1,1 -e, K n,1,1,1,1 -e, and K 2,1,1,1,1,1 -e are not intrinsically knotted. Abstract K 3,2,1,1,1 -(c,d) is equivalent to K 3,2,2,1 . The remaining 5 graphs each have 2 vertices connected to every other vertex. If those 2 vertices are deleted, the resulting graph is planar, so by lemma 4, they are not intrinsically knotted. Abstract 4.3. Proof of Adams' conjecture for 1-deficient graphs. Abstract Theorem 10. If G is a 1-deficient graph, and any one vertex and the edges coming into it are removed, the remaining graph is intrinsically linked. Abstract It suffices to verify the theorem for minimal examples of knotted 1-deficient graphs. k = 1: K 8 -e is intrinsically knotted. If we remove a vertex, we get either K 7 or K 7 -e, both of which are intrinsically linked. k = 2: K 5,5 -e is intrinsically knotted. If we remove a vertex, we get either K 5,4 -e or K 5,4 , both of which are intrinsically linked. Abstract k = 3: K 3,3,3 -e, K 4,3,2 -e, and K 4,4,1 -e are intrinsically knotted. If we remove a vertex from any of these graphs we will get K 3,3,2 -e, K 4,2,2 -e, K 4,3,1 -e, K 4,4 -e, or one of these without the removed edge. In any case, the result is intrinsically linked. k = 4: K 3,2,2,2 -e, K 4,2,2,1 -e, K 3,3,2,1 -e, and K 4,3,1,1 -e are intrinsically knotted. If we remove a vertex from any of these graphs we will get K 4,3,1 -e, K 3,3,2 -e, K 4,2,2 -e, K 2,2,2,2 -e, K 4,2,1,1 -e, K 3,3,1,1 -e, K 3,2,2,1 -e, or one of these without the edge removed. In all cases, the result is intrinsically linked. k = 5: K 2,2,2,2,1 -e, K 3,2,1,1,1 -(b,c), K 4,2,1,1,1 -e, K 3,3,1,1,1 -e, K 3,2,2,1,1 -e are intrinsically knotted. If we remove a vertex, we will get K 2,2,2,2 -e, K 3,2,1,1 -(b,c), K 4,2,1,1 -e, K 3,3,1,1 -e, K 3,2,2,1 -e, K 2,2,1,1,1 -(b,c), K 3,1,1,1,1 -(b,c), K 4,1,1,1,1 -e, K 3,2,1,1,1 -e, K 2,2,2,1,1 -e, or one of these without the removed edge. In all cases, the result is intrinsically linked. k = 6: K 2,2,1,1,1,1 -(b,c), K 3,1,1,1,1,1 -(b,c) , K 3,2,1,1,1,1 -e, K 2,2,2,1,1,1 -e, and K 4,1,1,1,1,1 -e are intrinsically knotted. If we remove a vertex, we will get K 2,2,1,1,1 -(b,c), K 3,1,1,1,1 -(b,c), K 4,1,1,1,1 -e, K 3,2,1,1,1 -e, K 2,2,2,1,1 -e, K 2,1,1,1,1,1 -(b,c), K 3,1,1,1,1,1 -e, K 2,2,1,1,1,1 -e, or one of these without the removed edge. In all cases, the result is intrinsically linked. k = 7: K 2,1,1,1,1,1,1 -e is intrinsically knotted. If we remove a vertex, we will get K 2,1,1,1,1,1 -e, K 1,1,1,1,1,1,1 -e, or one of these without the removed edge. All will be intrinsically linked. k ≥ 8: All 1-deficient graphs with 8 or more parts are intrinsically knotted. If we delete a vertex we will have a 1-deficient or complete partite graph with at least 7 parts, all of which are intrinsically linked. Abstract In this section we classify 2-deficient graphs with respect to intrinsic linking and knotting. We also show that Adams' conjecture holds for these graphs. Notation: We will expand the notation that we created in the last section by adding subscripts to the vertices. For example, if we are removing two edges between parts A and B of K 4,3,1 , there are 3 cases to be considered: deleting two edges that share a vertex from part A (K 4,3,1 -{(a 1 , b 1 ), (a 1 , b 2 )}), deleting two edges that share a vertex from part B (K 4,3,1 -{(a 1 , b 1 ), (a 2 , b 1 )}), and deleting two edges that share no vertices (K 4,3,1 -{(a 1 , b 1 ), (a 2 , b 2 )}). Also, in some cases, if we delete a particular edge we can then delete any other without affecting the classification of the resulting graph. For example, if we delete edge (b,c) from K 4,3,1 , we can then delete any other and still have an intrinsically linked graph; we will denote graphs obtained in this way by K 4,3,1 -{(b, c), e}. Furthermore, in some cases, we can delete any 2 edges and still have an intrinsically linked graph; for example, K 7 will be intrinsically linked no matter what 2 edges we delete. We denote these graphs K 7 -2e. Abstract Theorem 11. The 2-deficient graphs are classified with respect to intrinsic linking according to Tables 5 and 6 . Abstract Linked: Abstract K 7 -2e is intrinsically linked; there are 2 cases: Abstract For the first case, we can simply delete vertex b to get K 6 ; for the second case, we can contract edge (a, c) to get K 6 . Notice that any 2-deficient graph with 7 or more parts will have K 7 -2e as a minor, and will therefore be intrinsically linked. Abstract K 5,4 -2e is intrinsically linked; there are 3 cases. In each case, one removed edge will be (a 1 , b 1 ). If we simply delete vertex a 1 we will get K 4,4 or K 4,4 -e. Abstract By lemma 1, K 5,3,1 -2e, K 4,4,1 -2e, K 4,3,2 -2e, K 5,2,2 -2e, K 5,2,1,1 -2e, K 4,3,1,1 -2e, K 4,2,2,1 -2e, K 3,3,2,1 -2e, K 5,1,1,1,1 -2e, K 4,2,1,1,1 -2e, and K 3,3,1,1,1 -2e all have K 5,4 -2e as a minor, and are therefore intrinsically linked. Abstract K 3,3,3 -2e is intrinsically linked. Removing any 2 edges will result in a graph of the form K 3,3,3 -{(a, b), e}. If we delete vertex a, we will get K 3,3,2 , or K 3,3,2 -e, so K 3,3,3 -2e is intrinsically linked. Abstract K 2,2,2,2 -2e is intrinsically linked. All such graphs are of the form K 2,2,2,2 -{(a, b), e}. It them follows from lemma 1 that K 4,4 -e is a minor of K 2,2,2,2 -2e. c 1 ), (a 2 , c 1 )} 4,2,1,1-{(a 1 , b 1 ), (a 1 , b 2 )} 3,3,2-{(a 1 , c 1 ), (b 1 , c 1 )} 4,2,1,1-{(a 1 , b 1 ), (a 1 , c)} 3,3,2-{(a 1 , b 1 ), (b 2 , c 1 )} 4,2,1,1-{(a 1 , c), (a 1 , d)} 3,3,2-{(a 1 , c 1 ), (b 1 , c 2 ) } 3,3,1,1-{(b, c), e} 3,3,2-{ (a 1 , c 1 ), (a 1 , c 2 Abstract 3,2,2,1-{(a 1 , b 1 ), (a 2 , c 1 )} 2,2,2,2-2e 5,2,1,1-2e 4,3,1,1-2e 4,2,2,1-2e 3,3,2,1-2e not linked 6-2e 4,4-2e 4,3,1- Abstract 3,2,2-2e 3,2,2,1-{(a 1 , b 1 ), (a 1 , c 1 )} n,2,1-2e 2,2,2,1-2e 3,3,1-2e n,1,1,1-2e Table 5 . Intrinsic Linking of 2 Deficient Graphs By lemma 1, K 2,2,2,1,1 -2e and K 2,2,1,1,1,1 -2e have K 2,2,2,2 -2e as a minor, and are therefore intrinsically linked. K 3,1,1,1,1,1 -2e is intrinsically linked. All such graphs are of the form K 3,1,1,1,1,1 -{(a, b), e} or K 3,1,1,1,1,1 -{(b, c) , e}. The first case contains K 4,4 -e as a minor by lemma 1, and the second case is equivalent to K 3,2,1,1,1 -e, so K 3,1,1,1,1,1 -2e is intrinsically linked. Abstract By lemma 1, e}, K 4,1,1,1,1 -{(b, c) , e}, K 3,2,1,1,1 -{(a, c), e}, K 3,2,1,1,1 -{(b, c), e}, and K 3,2,1,1,1 -{(c, d), e} all have K 4,4 -e as a minor, and are therefore all intrinsically linked. K 3,3,1,1 -{(c, d), e}, and K 3,2,2,1 -{(c, d), e} have K 3,3,2 -e as a minor by lemma 1, so they are intrinsically linked. 1,1,1,1-{(b, c), e} 3,1,1,1,1,1-2e 4,1,1,1,1-{(a 1 , b), (a 1 , c)} 2,2,1,1,1,1-2e 3,2,1,1,1-{(a, c), e} 3,2,1,1,1-{(b, c), e} 3,2,1,1,1-{(c, d), e} 3,2,1,1,1-{(a 1 , b 1 ), (a 1 , b 2 )} 3,2,1,1,1-{(a 1 , b 1 ), (a 2 , b 1 ) } 2,2,2,1,1-2e 5,1,1,1,1-2e 4,2,1,1,1-2e 3,3,1,1,1-2e not linked 2,2,1, Table 6 . Intrinsic Linking of 2 Deficient Graphs (cont.) K 4,3,1 -{(a 1 , b 1 ), (a 1 , b 2 )} and K 4,3,1 -{(a 1 , b 1 ), (a 1 , c)} both have K 3,3,1 as a minor; simply delete vertex a 1 . So both are intrinsically linked. b 2 )} as a minor, so they are all intrinsically linked. (Notice that for the case of K 3,2,2,1 and K 3,2,1,1,1 -{(a 1 , b 1 ), (a 2 , b 1 )}, once the parts are combined, the labels (a and b) of some of the vertices switch.) K 3,3,2 -{(a 1 , b 1 ), (a 1 , b 2 )} and K 3,3,2 -{(a 1 , b 1 ), (b 2 , c 1 )} have K 3,2,1,1 as a minor. To see this, simply contract edge (a 1 , c 1 ). So both are intrinsically linked. Abstract By lemma 1, c 1 ) , (a 2 , c 1 )} and K 3,3,2 -{(a 1 , c 1 ), (b 1 , c 1 )} both have K 3,3,1 as a minor; simply delete vertex c 1 . So both are intrinsically linked. K 3,3,2 -{(a 1 , c 1 ), (b 1 , c 2 )} is intrinsically linked. Delete the remaining edges between c 1 and A and between c 2 and B. The result is K 4,4 − e where the missing edge is between vertices c 1 and c 2 . Abstract K 3,3,2 − {(a 1 , c 1 ), (a 1 , c 2 )} is intrinsically linked. In figure 7 , at left is a Petersen graph, and at right is that same graph with four edges added. As we can see, this is K 3,3,2 − {(a 1 , c 1 ), (a 1 , c 2 )}. Abstract K 4,2,2 -{(a 1 , b 1 ), (a 1 , b 2 )} is intrinsically linked; contract edge (a 1 , c 1 ) to get K 3,2,1,1 INTRINSIC KNOTTING AND LINKING OF ALMOST COMPLETE PARTITE GRAPHS 13 Figure 7 . K 3,3,2 − {(a 1 , c 1 ), (a 1 , c 2 )} is Intrinsically Linked Abstract 2 )} as a minor by lemma 1. Abstract as a minor by lemma 1. Abstract )} has K 6 as a minor; simply contract edge (a 1 , b 1 ). Abstract as a minor by lemma 1. Abstract , (a 1 , c)} has K 6 as a minor; simply delete vertex a 1 . Abstract Not Linked: Abstract The following graphs are already known not to be intrinsically linked if we add one more edge, so they are naturally not intrinsically linked: K 6 -2e (or K 1,1,1,1,1,1 -2e), K n,3 -2e, K 3,2,2 -2e, K n,2,1 -2e, K 3,3,1 -2e, K 2,2,2,1 -2e, K n,1,1,1 -2e, K 3,2,1,1 -{(a, b), e}, K 3,2,1,1 -{(a, c), e}, K 3,2,1,1 -{(c, d), e}, K 2,2,1,1,1 -{(a, b), e}, K 2,2,1,1,1 -{(c, d), e}, K 3,1,1,1,1 -{(a, b), e}, K 2,1,1,1,1 -2e. Abstract 1 )}, and K 4,3,1 -{(a 1 , b 1 ), (a 2 , b 2 )} all have 1 vertex connected to every other. In each of these, if we delete that vertex we get a planar graph; so, by lemma 2, none are intrinsically linked. Abstract } is equivalent to K 3,2,2 , so it is not intrinsically linked. Abstract , (a 2 , c)} by lemma 1; simply combine parts D and E. Abstract } by lemma 1; simply combine parts C and D. Abstract 1 )}, and K 4,2,1,1 -{(a 1 , b 1 ), (a 2 , c)} respectively by lemma 1. K 4,2,2 − {(a 1 , b 1 ), (a 1 , c 1 )} is a minor of K 3,2,2,1 − {(a 1 , b 1 ), (a 1 , c 1 )} and is, therefore, not intrinsically linked. Abstract } is not intrinsically linked by the corollary to lemma 2; if you delete vertex a 2 , the result is a planar graph. Abstract K 4,3,1 -{(a 1 , c), (a 2 , c)} and K 4,3,1 -{(a 1 , b 1 ), (a 2 , c)} are minors of K 4,2,1,1 -{(a 1 , c), (a 2 , c)} and K 4,2,1,1 -{(a 1 , b 1 ), (a 2 , c)} respectively by lemma 1, and therefore are not intrinsically linked. Abstract K 4,4 -2e is a minor of K 4,4 -e, which is minor minimally intrinsically linked, so it is not intrinsically linked. Abstract 4,2,2,1,1-2e 4,2,2,2-2e 3,3,2,1,1-2e 3,3,2,2-2e 5,2,2,1-2e 4,3,2,1-2e 3,3,3,1-2e 5,3,1,1-2e 4,4,1,1-2e not knotted 7-2e n,4-2e 3,3,3-{(a 1 , b 1 ),(b 1 , c 1 )} 3,2,2,2-{(a 1 , b 1 ),(a 1 , c 1 )} 3,2,1,1,1-{(a, b), e} 3,3,3-{(a 1 , b 1 ),(a 2 , b 2 )} 3,2,2,2-{(a 1 , b 1 ),(a 2 , b 2 )} 3,2,1,1,1-{(a, c), e} Abstract 4,3,1,1-{(a 1 , c),(a 2 , c)} n,3,1-2e 3,3,1,1-2e 2,2,2,2-2e 3,2,2,1-2e n,2,1,1-2e 1,1,1,1,1-{(b, c), e} 3,1,1,1,1,1,1-2e 4,1,1,1,1,1-{(a 1 , b),(a 1 , c)} 2,2,1,1,1,1,1-2e 3,2,1,1,1,1-{(a, c), e} 3,2,1,1,1,1-{(b, c), e} 3,2,1,1,1,1-{(c, d), e} 3,2,1,1,1,1-{(a 1 , b 1 ), (a 1 , b 2 )} 3,2,1,1,1,1-{(a 1 , b 1 ), (a 2 , b 1 )} 2,2,2,1,1,1-2e 5,1,1,1,1,1-2e 4,2,1,1,1,1-2e 3,3,1,1,1,1-2e not knotted 2,2,1, Theorem 12. The 2-deficient graphs are classified with respect to intrinsic knotting according to Tables 7 and 8 . Abstract Knotted: Abstract In the first case, delete vertex b to get K 7 ; in the second, contract edge (a, c) to get K 7 . So K 8 -2e is intrinsically knotted. Note that any 2-deficient graph with 8 or more parts will have K 8 -2e as a minor. Abstract K 5,5 -2e has 2 cases. As shown in figure 8 , by splitting vertex v and then adding the dashed lines, it can be seen that, in either case, K 5,5 -2e has H 9 (from [6]) as a minor. Abstract By lemma 1, K 5,4,1 -2e, K 5,3,2 -2e, K 3,3,2,2 -2e, K 5,2,2,1 -2e, K 4,3,2,1 -2e, K 5,3,1,1 -2e, K 4,4,1,1 -2e, K 5,2,1,1,1 -2e, K 4,3,1,1,1 -2e, K 4,2,2,1,1 -2e, K 3,3,2,1,1 -2e, K 5,1,1,1,1,1 -2e, K 4,2,1,1,1,1 -2e, and K 3,3,1,1,1,1 -2e all contain K 5,5 -2e as a minor and are therefore intrinsically knotted. Abstract K 4,3,3 -2e is intrinsically knotted. In all cases, there is one removed edge connected to vertex b 1 ; delete that vertex to get K 4,3,2 -e. K 3,3,3,1 -2e has K 4,3,3 -2e as a minor by lemma 1, so it is intrinsically knotted. K 4,4,2 -2e is intrinsically knotted. In all cases, there is one removed edge connected to vertex a 1 ; delete vertex a 1 to get K 4,3,2 -e. Abstract By lemma 1, K 4,2,2,2 -2e has K 4,4,2 -2e as a minor. Figure 8 . H 9 is a Minor of K 5,5 -2e K 2,2,2,2,1 -2e is intrinsically knotted. In all cases, there will be an edge missing between A and B or between D and E. If we combine parts A and B in the first case, we get K 4,2,2,1 -e or K 4,2,2,1 , and if we combine parts D and E in the second case, we get K 3,2,2,2 -e or K 3,2,2,2 . So, in either case, K 2,2,2,2,1 -2e has an intrinsically knotted minor. Abstract By lemma 1, K 2,2,2,1,1,1 -2e and K 2,2,1,1,1,1,1 -2e have K 2,2,2,2,1 -2e as a minor. K 3,1,1,1,1,1,1 -2e is intrinsically knotted. There is either an edge missing between parts A and B or between parts B and C. In the first case, we can combine A and B to get K 4,1,1,1,1,1 -e or K 4,1,1,1,1,1 , and in the second, we can combine parts B and C to get K 3,2,1,1,1,1 -e or K 3,2,1,1,1 . Abstract By lemma 1, As shown in figure 3 , H 9 is a minor of K 3,3,3 . If we simply add fewer edges, we see that K 3,3,3 -{(a 1 , b 1 ), (a 1 , b 2 )} and K 3,3,3 -{(a 1 , b 1 ), (b 2 , c 1 )} are intrinsically knotted. K 3,3,2,1 -{(a 1 , b 1 ), (a 1 , b 2 )}, K 3,3,2,1 -{(b 1 , c 1 ), (b 1 , c 2 )}, K 3,3,1,1,1 -{(a 1 , b 1 ), (a 2 , b 1 )}, K 3,2,2,1,1 -{(a 1 , b 1 ), (a 1 , b 2 )}, K 3,2,2,1,1 -{(a 1 , b 1 ), (a 2 , b 1 )}, K 3,2,1,1,1,1 -{(a 1 , b 1 ), (a 1 , b 2 )}, K 3,2,1,1,1,1 -{(a 1 , b 1 ), (a 2 , b 1 )}, and K 3,3,2,1 -{(a 1 , c 1 ), (a 2 , c 1 )} have K 3,3,3 -{(a 1 , b 1 ), (a 1 , b 2 )} as a minor by lemma 1. K 3,2,2,1,1 -{(a 1 , b 1 ), (a 2 , c 1 )}, K 3,3,2,1 -{(a 1 , b 1 ), (a 2 , c 1 )}, and K 3,3,2,1 -{(a 1 , c 1 ), (b 1 , c 2 )} have K 3,3,3 -{(a 1 , b 1 ), (b 2 , c 1 )} as a minor by lemma 1. Abstract As shown in figure 6 , H 9 is a minor of K 4,4,1 . If we simply add fewer edges, we can see that K 4,4,1 -{(a 1 , c), (b 1 , c)} and K 4,4,1 -{(a 1 , b 1 ), (b 1 , c)} are intrinsically knotted. K 4,2,2,1 -{(a 1 , b 1 ), (a 1 , d)}, K 4,3,1,1 -{(a 1 , b 1 ), (a 1 , c)}, K 4,2,1,1,1 -{(a 1 , b 1 ), (a 1 , c)}, K 4,2,1,1,1 -{(a 1 , c), (a 1 , d)}, K 4,1,1,1,1,1 -{(a 1 , b), (a 1 , c)}, and K 4,3,1,1 -{(a 1 , c), (a 1 , d)} have K 4,4,1 -{(a 1 , b 1 ), (b 1 , c)} as a minor by lemma 1. Abstract H 9 is a minor of K 4,3,2 as shown in figure 5 . If we add 2 fewer edges, we can see that K 4,3 Introduction We say that a graph is intrinsically knotted (respectively, linked) if every tame embedding of the graph in R 3 contains a non-trivially knotted cycle (respectively, pair of non-trivially linked cycles). Robertson, Seymour, and Thomas [9] demonstrated that intrinsic linking is determined by the seven Petersen graphs. A graph is intrinsically linked if and only if it is or contains one of the seven as a minor. They also showed [8] that a similar, finite list of graphs exists for the intrinsic knotting property. However, determining this list remains difficult. Introduction It is known [2, 4, 6, 7] that K 7 and K 3,3,1,1 along with any graph obtained from these two by triangle-Y exchanges is minor minimal with respect to intrinsic knotting. Recently Foisy [5] has added a new minor minimal graph to the list. Foisy's example is particularly interesting from our perspective as it provides a counterexample to the "unsolved question" posed in Adams' [1] book: Is it true that if G [a graph] is intrinsically knotted and any one vertex and the edges coming into it are removed, the remaining graph is intrinsically linked? Introduction While Adams' conjecture is not true in general, it does appear to hold for a wide array of graphs, particularly graphs that are "almost" complete. We will say a graph is k-deficient if it is a complete or complete partite graph with k edges removed. In the current article we verify Adams' conjecture for 0-, 1-, and 2-deficient graphs. This can be seen as the first few steps in a project to find a counterexample to Adams' conjecture of minimum deficiency. However, as Foisy's counterexample is 13-deficient, there is a long way to go in this program. Introduction More promising is the search for a counterexample on a minimum number of vertices. Since K 7 is a minor minimal intrinsically knotted graph, it is the only graph on 7 or fewer vertices that is intrinsically knotted. In the current paper, we show that there are twenty intrinsically knotted graphs on 8 vertices. These all satisfy Adams' conjecture, so a minimal counterexample to the conjecture must have between 9 vertices and the 13 of Foisy's graph. Introduction In classifying intrinsic knotting of various families, we have made use of the known minor minimal examples derived from K 7 and K 3,3,1,1 by triangle-Y exchanges. In particular, we include here a table of the 25 graphs obtained from K 3,3,1,1 ([6] includes the table built on K 7 ). Note that there are no new examples of minor minimal intrinsically knotted graphs to be found among 0-, 1-, and 2-deficient graphs and graphs on 8 vertices. Introduction The paper is organized as follows. Following this introduction, Section 2 presents some fundamental lemmas and the table of graphs obtained from K 3,3,1,1 by triangle-Y exchanges. In Sections 3,4, and 5 we investigate 0-, 1-, and 2-deficient graphs respectively. In each case we classify the graphs with respect to intrinsic knotting and linking and demonstrate that they satisfy Adams' conjecture. In Section 6 we classify intrinsically knotted graphs on 8 vertices and verify that they too satisfy Adams' conjecture. We complete the paper by formulating the analogue to a question Sachs asked about intrinsic linking. We show that if 5 ≤ n ≤ 8, a graph on n vertices that is not intrinsically knotted will have at most 5n − 15 edges and ask if this is true more generally: Question: Is there a graph on n vertices that is not intrinsically knotted and has more than 5n − 15 edges? 2. Lemmas and graphs derived from K 3,3,1,1 Introduction In this section we present some useful lemmas as well as a table of graphs derived from K 3,3,1,1 by triangle-Y exchanges. Let us begin with some notation. We will use K a1,a2,...,ap to denote a complete partite graph with p parts containing respectively a 1 , a 2 , . . . , a p vertices. Permuting the a i results in the same graph. We will usually write the parts in descending order: a 1 ≥ a 2 ≥ . . . ≥ a p . The complete graph on n vertices is denoted K n . Introduction Recall that a minor of a graph G is the resultant graph after performing a finite number of vertex or edge deletions and edge contractions on G. An example of an edge contraction is shown in figure 1 (moving from left to right in the figure). Moving from right to left in the figure is known as splitting a vertex. We say a graph G is minor minimal with respect to a property if G exhibits the property but no minor of G does. For example, the seven Petersen graphs are the only graphs minor minimal with respect to intrinsic linking. An intrinsically linked graph must either be a Petersen graph or contain one as a minor. Introduction The analogous list of graphs for intrinsic knotting is incomplete at this time. We do know that the list is finite [8] and if G is in the list, so is any graph obtained from G by triangle-Y exchanges [7] . To perform a triangle-Y exchange on a graph, find 3 vertices that are all connected to one another, delete the three edges between them, and replace with a single vertex connected to all 3 vertices of the triangle. Kohara and Suzuki [6] have provided a list of the 13 graphs arising from K 7 by triangle-Y exchanges. They state that these graphs are minor-minimal with respect to intrinsic knotting and remark that there are 25 graphs that can be constructed from K 3,3,1,1 by triangle-Y exchanges. We present these graphs in figure 2. Since Foisy [4] showed that K 3,3,1,1 is intrinsically linked it follows [6] that all 26 graphs in the figure are minor minimal with respect to intrinsic knotting. Introduction The graphs in figure 2 are organized into rows having equal numbers of vertices. The arrows indicate that a triangle-Y exchange has occurred. A dashed arrow means that the triangle-Y exchange will result in a different projection of the graph than that shown in the figure. Note that graphs B 13 , C 13 , and A 14 contain no triangles. Most graphs in the figure can be shown to be different from the others by examining the set of vertex degrees. The exceptions
{'paper_id': '1121732', 'title': 'Intrinsic Knotting and Linking of Almost Complete Partite Graphs', 's2_url': 'https://api.semanticscholar.org/CorpusID:1121732', 'source': 'S2ORC'}