{'fraction_non_alphanumeric': 0.06490929705215419, 'fraction_numerical': 0.016546201814058956, 'mean_word_length': 3.3786844554762645, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Split Graphs and Nordhaus-Gaddum Graphs

A graph G is an NG-graph if \chi(G) + \chi(G complement) = |V(G)| + 1. We characterize NG-graphs solely from degree sequences leading to a linear-time recognition algorithm. We also explore the connections between NG-graphs and split graphs. There are three types of NG-graphs and split graphs can also be divided naturally into two categories, balanced and unbalanced. We characterize each of these five classes by degree sequence. We construct bijections between classes of NG-graphs and balanced and unbalanced split graphs which, together with the known formula for the number of split graphs on n vertices, allows us to compute the sizes of each of these classes. Finally, we provide a bijection between unbalanced split graphs on n vertices and split graphs on n-1 or fewer vertices providing evidence for our conjecture that the rapid growth in the number of split graphs comes from the balanced split graphs.


Introduction
For a graph G, the number of vertices in a largest clique in G is denoted by ω(G) and the number of vertices in a largest stable set (independent set) in G is denoted by α(G). We denote the complement of G by G and the graph induced in G by X ∈ V (G) by G[X]. We write nbh(x) to denote the set of vertices adjacent to vertex x. For a set of graphs, C, we denote by C n the set of graphs in C with n vertices.
We call G a Nordhaus-Gaddum graph or NG-graph if G satisfies the maximum value of this inequality; i.e., χ(G) + χ(Ḡ) = |V (G)| + 1. Finck [9] and Starr and Turner [16] provide two different characterizations of NG-graphs. More recently, Collins and Trenk [7] define the ABC-partition of a graph and characterize NG-graphs in terms of this partition.
When it is unambiguous, we write A = A G , B = B G , C = C G .
Theorem 2. (Collins and Trenk [7]) A graph G is an NG-graph if and only if its ABC-partition satisfies (i) A = ∅ and G[A] is a clique, a stable set, or a 5-cycle (ii) G[B] is a clique (iii) G[C] is a stable set (iv) uv ∈ E(G) for all u ∈ A, v ∈ B (v) uw ∈ E(G) for all u ∈ A, w ∈ C.
By (i) of Theorem 2, there are three possible forms of an NG-graph. (See Figure 1.)

Definition 3. We say that G is an NG-1 graph if G[A] is a clique, an NG-2 graph if G[A] is a stable set, and an NG-3 graph if G[A]
is a 5-cycle. We also let N G-1 be the set of NG-1 graphs and likewise define the sets N G-2 and N G-3.
The characterization in Theorem 2 not only provides a clear description of NGgraphs but it also lends itself to an O(|V (G)| 3 )-time recognition algorithm for NGgraphs [7]. More importantly for this article, it shows that NG-graphs are related to split graphs and pseudo-split graphs. A split graph is a graph G whose vertex set can be partitioned as V (G) = K ∪ S, where K induces a clique and S induces a stable set in G. A detailed introduction to this class appears in [11]. Split graphs are a well-known class of perfect graphs, and thus χ(G) = ω(G) for split graphs. Split graphs also have elegant characterization theorems. Földes and Hammer [10] give a forbidden subgraph characterization of split graphs as those graphs with no induced 2K 2 , C 4 or C 5 . Split graphs also have a degree sequence characterization due to Hammer and Simeone [12] which we present in Theorem 14. This latter characterization implies that split graphs can be recognized in linear time.
Blázsik et al. [3] consider the class of graphs that do not contain C 4 and 2K 2 as induced subgraphs, later referred to as pseudo-split graphs [13]. They show that like split graphs, pseudo-split graphs can be defined in terms of vertex sets partitions. In particular, a graph G is a pseudo-split graph if and only if V (G) can be partitioned into three parts so that (i) first part is either empty or induces a 5-cycle, the second part a clique, the third part a stable set and (ii) whenever the first part is a 5-cycle, every vertex in the first part is adjacent to every vertex in the second part but there are no edges between the first part and the third part. Interestingly, Blázsik et al. also note that pseudo-split graphs are almost extremal in terms of the Nordhaus-Gaddum inequality because for any such graph G, χ(G) + χ(Ḡ) ≥ |V (G)|. In the process of proving this result, they show that if G contains an induced 5-cycle then χ(G) + χ(Ḡ) ≥ |V (G)| + 1 and thus G is an NG-graph.
The next result follows from Theorem 2 and the characterization of pseudo-split graphs discussed above. In particular, a graph is an NG-3 graph if and only if it is a pseudo-split graph containing an induced 5-cycle.

Remark 4.
A graph is a pseudo-split graph if and only if it is a split graph or an NG-3 graph.
Proposition 5. Let G be an NG-graph. Then G is a split graph if and only if G ∈ (N G-1 ∪ N G-2).
Proof. By definition, NG-3 graphs contain an induced C 5 , hence are not split graphs. Now suppose G ∈ (N G-1 ∪ N G-2) and let its ABC-partition be V (G) = A ∪ B ∪ C. If G ∈ N G-1, let K = A ∪ B and S = C and otherwise, G ∈ N G-2, and we let K = B and S = A ∪ C. In either case, using Theorem 2, we get a partition of V (G) into a clique K and a stable set S, so G is a split graph.
Not all split graphs are NG-graphs. Indeed, the relationship between these classes, as well as the results in Remark 4 and Proposition 5, are shown in Figure 2. We will define the classes of balanced and unbalanced split graphs in the next section.
Building on the work of Blázsik et al. [3], Maffray and Preissmann [13] present a degree sequence characterization for NG-3 graphs. They combine this with the similar characterization for split graphs to get a linear-time recognition algorithm for pseudo-split graphs. We will discuss similar algorithms for NG-graphs in Section 3.
Finally, we note that Theorem 2 is very much related to the notion of graph decomposition that was studied systematically by Tyshchevich [17]. A graph is said to be decomposable if its vertex set can be partitioned into three parts A, B and C so that A = ∅ and B ∪ C = ∅ and conditions (ii) to (v) of Theorem 2 are satisfied. Thus, every NG-graph is decomposable except when it is a single vertex or a 5-cycle. Chvátal and Hammer [5], Blázik et al. [3] and Barrus [1,2] also characterized various graph classes in terms of their decompositions.
Our main objective is to explore the connections between NG-graphs and split graphs. In Section 2, we study split graphs through the lens of NG-graphs. In particular, we determine which split graphs are NG-graphs and show how their ABCpartitions relate to their clique-stable set partitions. In Section 3, we do the opposite and consider NG-graphs through the lens of split graphs. We provide degree characterizations for NG-1 and NG-2 graphs that are quite similar to the one for split graphs. We also present a degree characterization of NG-3 graphs that is equivalent to the one in [13]. These results show that, like split graphs and pseudo-split graphs, NG-graphs have a linear-time recognition algorithm. In Section 4 we present various kinds of bijections including those between subclasses of NG-graphs and subclasses of split graphs. Finally, in Section 5, we take advantage of these bijections and present formulas for the number of graphs on n vertices in each of the graph classes we studied. Our work comparing NG-graphs to split graphs leads to a theorem only about split graphs: that for n ≥ 1, the number of unbalanced split graphs on n vertices is equal to the number of split graphs on n − 1 or fewer vertices.
Unbalanced split graphs Figure 2: A partition of the class of pseudo-split graphs into NG-graphs and split graphs.

Split Graphs and NG-graphs
In this section we consider the set S of split graphs and discuss connections to NGgraphs. A KS-partition of a split graph G is a partition of the vertex set as V (G) = K ∪ S where K is a clique and S is a stable set. Just as it is helpful to characterize NG-graphs into the classes N G-1, N G-2 and N G-3 based on their ABC-partition, it is also useful to categorize split graphs based on their KS-partitions. Definition 6. A split graph G is balanced if it has a KS-partition satisfying |K| = ω(G) and |S| = α(G) and unbalanced otherwise. We denote the set of balanced split graphs by B and the set of unbalanced split graphs by U. A KS-partition is S-max if |S| = α(G) and K-max if |K| = ω(G).
Unlike ABC-partitions, KS-partitions of a split graph are not always unique. The terms balanced and unbalanced in Definition 6 refer to a split graph G while the terms K-max and S-max refer to a particular KS-partition of G. The next theorem follows from the work of Hammer and Simeone [12] and appears in [11]. We include a proof for completeness. Theorem 7. (Hammer and Simeone [12]) For any KS-partition of a split graph G, exactly one of the following holds: (i) |K| = ω(G) and |S| = α(G).
(unbalanced, K-max) Moreover, in (ii) there exists s ∈ S so that K ∪ {s} is complete and in (iii) there exists k ∈ K so that S ∪ {k} is a stable set.
Proof. Partition the vertex set of G as V (G) = K ∪ S where K is a clique and S is a stable set. If both K and S are maximum size then |K| = ω(G) and |S| = α(G), resulting in case (i). If K is not maximum size, then ω(G) = |K| + 1 because only one vertex of S can be part of a clique. In this case, there must exist s ∈ S adjacent to each vertex in K. Then no vertex of K can be added to S to make a larger stable set, and at most one vertex of K can be in any stable set, so S is maximum size. Thus |S| = α(G), resulting in case (ii), and moreover, K ∪ {s} is complete. Similarly, if S is not maximum size, the result is case (iii).
In Proposition 5, we showed which NG-graphs are split graphs. In the next theorem we show which split graphs are NG-graphs.
Theorem 8. The following are equivalent for a split graph G.
The next remark follows from Proposition 5 and Theorem 8. The Venn diagram in Figure 2 shows the relationships we have proven about NG-graphs and split graphs.
Our knowledge of NG-graphs allows us to refine the Hammer/Simeone conditions in Theorem 7. In particular, we can characterize all KS-partitions of a split graph and for split graphs with more than one KS-partition (unbalanced) it is precisely the vertices in A G that can be moved between K and S. Theorem 10. Suppose G is an unbalanced split graph and let V (G) = A ∪ B ∪ C be its ABC-partition. The KS-partitions of G can be characterized as follows.
• If G ∈ N G-1, the partitions are Proof. Since G is an unbalanced split graph, we know that G is also an NG-graph by Theorem 8. Indeed, by Proposition 5, it is an NG-1 graph or an NG-2 graph. We will give the argument in the case in which G is an NG-1 graph, that is, G[A] is a clique. The case in which G is an NG-2 graph is similar.
Let K = A ∪ B and S = C. We claim that |K| = ω(G), that is, this is a K-max partition of G. At most one vertex of stable set C can be in any clique of G but no vertex of C can be added to K because vertices of C are not adjacent to vertices in A and A = ∅. Thus |K| = ω(G) as desired and by Theorem 7, |S| = α(G) − 1.
We next show that this is the only K-max partition of G. As before, at most one vertex of C can be in a clique, so if there were a different K-max partition, we would have to move one vertex c ∈ C from S to the clique K and remove one vertex from K = A ∪ B to S. Since vertices in C are not adjacent to vertices in A, we must remove all vertices in A from K in order to retain a clique, thus |A| = 1. But in this case, the vertex c and the vertex a ∈ A have the same neighbor set (namely, all vertices in B) and thus the same degree, violating Definition 1.
Next we characterize the S-max partitions. Take any a ∈ A and let Finally, we show these are the only S-max partitions of G. Since A ∪ B is a clique in G, at most one vertex of A ∪ B can be in any stable set. If a vertex b ∈ B were added to S to form a larger stable set, then b would have the same degree (namely |A| + |B| − 1) as each vertex in A, violating Definition 1.
The next corollary follows directly from Theorem 10 and allows us to conclude that there are exactly (|A| + 1) KS-partitions of an unbalanced labeled split graph. In contrast, there is a unique KS-partition of a balanced split graph as shown in Proposition 12.
Corollary 11. Suppose G is an unbalanced split graph and let V (G) = A ∪ B ∪ C be its ABC-partition. Then if we consider G to be a labelled graph, it has either a unique K-max partition and exactly |A| distinct S-max partitions or a unique S-max partition and exactly |A| distinct K-max partitions.
Proposition 12. Each balanced split graph has a unique KS-partition.
Proof. Let G be a balanced split graph and fix a KS-partition of G with |K| = ω(G) and |S| = α(G). For a contradiction, suppose K ′ S ′ is a different KS-partition of G. Since K and S are already of maximum size and at most one vertex of S can be in a clique and at most one vertex of K can be in a stable set, we know K ′ = K ∪{y}−{x} and S ′ = S ∪ {x} − {y} for some x ∈ K and y ∈ S. Now K and K ′ are cliques but K ∪ {y} has ω(G) + 1 vertices and is not a clique, so xy ∈ E(G). But then x is not adjacent to any vertex in S, so S ∪ {x} is a stable set of size α(G) + 1, a contradiction.
We use the term "unlabeled graphs" in the remainder of the paper to refer to isomorphism classes of graphs as in [18].
Corollary 13. Each unlabeled unbalanced split graph has exactly two KS-partitions, one is K-max and the other is S-max.
Proof. Let G be an unbalanced split graph. Fix a KS-partition of G. If it is S-max, then we can move a vertex from S to K, as in the proof of Theorem 7, to obtain a can be in a clique, there exists x ∈ S 1 and y ∈ K 1 such that Then there is an automorphism of G obtained by switching vertices x and y and leaving the remaining vertices unchanged. This contradicts our assumption that K 1 S 1 and K 2 S 2 are not isomorphic. The proof for two non-isomorphic S-max partitions is similar.

Degree sequence characterizations
We begin with the Hammer and Simeone result showing that split graphs can be recognized solely from their degree sequences. The proof serves as a foundation for the proofs of Theorems 17 and 22.
G is a split graph, equality (1) holds and ω(G) = m as desired. Thus we may assume G is not complete, thus d n < n − 1 and m ≤ n − 1.
First we assume that G satisfies the equality (1) in Theorem 14. We let and |E 3 | = 0. Thus K is a clique and S a stable set as desired.
Conversely, let G be a split graph and by Theorem 7 we can fix a K-max partition of G. As before, let E 1 be the edge set of G[K], E 2 be the set of edges with one endpoint in K and the other in S, and E 3 be the edge set of G[S]. Since K is a clique, deg(v) ≥ |K| − 1 for each v ∈ K and since S is a stable set and K is a maximum size clique, deg(v) ≤ |K| − 1 for each v ∈ S. Thus m = k and without loss and S a stable set. Thus equality holds in (1).
We will see in Examples 18 and 19 that index m is either the first or last index i for which d i = m − 1. The next theorem shows that this is true for all split graphs.
But vertices v m and v m−1 each have degree m − 1 and each already has m − 1 neighbors in K, a contradiction.
In Theorems 17 and 22, we characterize the graphs in N G-1, N G-2, and N G-3 by their degree sequences.
Similarly, G ∈(N G-2) n if and only if it satisfies (1) and , then G is a split graph by Proposition 5. Conversely, if G satisfies (1), it is a split graph by Theorem 14. Split graphs are perfect, so χ(G) = ω(G).
. . , v n }. By Theorem 14 and Remark 15, we know K is a clique, S is a stable set and KS is a K-max partition of G. Thus ω(G) = |K| = m and χ(G) = m.
For the forward direction, assume G ∈ (N G-1 ∪ N G-2). Then G is an unbalanced split graph by Theorem 8 and thus satisfies (1) of Theorem 14. It remains to show that G ∈ N G-1 implies (2) and G ∈ N G-2 implies (2 ′ ).
First assume G ∈ N G-1. Then by Theorem 10, the partition K = A∪B, S = C is the unique K-max partition of G. Since A = ∅ for NG-graphs and v m has the smallest degree among vertices in K, we know that v m ∈ A and thus d m = χ(G) − 1 = m − 1. Moreover, v m+1 ∈ C, thus by Definition 1, In the first instance, where (2) holds, each of the vertices in S has degree at most m − 2 and m − 2 < χ(G) − 1. Hence C = S and A ∪ B = K. Each vertex in A is adjacent to the other m − 1 vertices in K, thus is not adjacent to any vertex in C, which proves that G ∈ N G-1.
In Example 18. Let G 1 be the NG-1 graph whose ABC-partition is , v 10 }, and where the edge set between B and C is The table below    The following characterization of the class of balanced split graphs follows immediately from Theorem 14 and Corollary 20. Observe that Corollary 21 does not make any reference to NG-graphs.
Corollary 21. Let G = (V, E) be a graph with degree sequence d 1 ≥ d 2 ≥ · · · ≥ d n and m = max{i : d i ≥ i − 1}. Then G is a balanced split graph if and only if it satisfies In the next theorem, we characterize the class N G-3 by degree sequences. In this instance, i is the middle index of five in which d i = m − 1. An equivalent result appears in [13].
Theorem 22. Let G = (V, E) be a graph with degree sequence d 1 ≥ d 2 ≥ · · · ≥ d n and let m = max{i : d i ≥ i − 1}. Then G ∈(N G-3) n if and only if the following conditions hold: First we suppose that G satisfies the two conditions and show G is an NG-3 graph. Partition V (G) into sets B, A, C as follows and let X = A ∪ B: We will show that this is the ABC-partition of G. Partition the edge set of G as and E 2 is the set of edges in G with one endpoint in X and the other in C. Summing vertex degrees in X and in C we get Using condition (i) in the hypothesis, we get Since |X| = m + 2, each vertex in X has degree in G[X] of at most m + 1, and by condition (ii), the five vertices in A have degree m − 1 in G, thus their degree is at most m − 1 in G[X]. So summing degrees of vertices in the induced graph G[X] we get Combining this with equation (2) we get |E 3 | = 0 and conclude that C is a stable set. Now using |E 3 | = 0 in (2) we get |E 1 | = m+2 Also, because C is a stable set and there are no edges between A and C, n i=m+3 d i = |E 2 |. Combining these gives the first condition in Proposition 22.
Example 23. Let G 3 be the NG-3 graph formed from G 1 in Example 18 by expanding A to be a 5-cycle. Thus, m = 6 which is the middle index of the 5 vertices of degree d m = 5. We know that split graphs are not NG-3 graphs by Proposition 5. Theorem 16 shows that the second condition of Theorem 22 is never satisfied for a split graph. The following example shows that it is possible for a split graph to satisfy the first condition of Theorem 22.
Example 24. Let G be the split graph with KS partition Notice that the first condition in Theorem 22 is satisfied, but the second is not.
Finally, since sorting the degrees of the vertices of a graph can be done in linear time using stable sort, Theorems 17 and 22 imply the next corollary.
Corollary 25. Given a graph G, determining if G is an NG-1, NG-2 or an NG-3 graph can be done in linear time.

Bijections
Throughout this section we are considering unlabeled graphs. Definition 3 divides the set of NG-graphs into three categories: N G-1, N G-2, and N G-3, according to whether the set A of the ABC-partition induces a clique, a stable set or a 5-cycle. The first two categories overlap in the case where |A| = 1. By removing this intersection as a separate class, we can partition the set of NG-graphs into four classes: (N G-1 − N G-2), (N G-2 − N G-1), (N G-1 ∩ N G-2) and N G-3. Recall that we also divide split graphs (S) into balanced (B) and unbalanced (U). Let (T ) ≤n be the set of split graphs on n or fewer vertices and recall that (C) n denotes the set of graphs with n vertices in a class C.
In this section we provide bijections between classes of NG-graphs and classes of split graphs. In Section 5, we use these results to count the number of graphs in each class. Table 1 summarizes the bijection results in this section and Theorem 26 records the locations of each of the proofs. The proofs are organized by the type of bijection used.
Theorem 26. There is a bijection between any two classes of graphs that appear in the same row of Table 1  We begin with a lemma that identifies the type of KS-partition that results from removing A G from an NG-graph G.
Lemma 27. Let G be an NG-graph and V (G) = A∪B∪C be its ABC-partition. Then G − A is a split graph and has a KS-partition with K = B and S = C. Moreover, Proof. It is immediate that G −A is a split graph and that K = B, S = C constitutes a KS-partition of G − A. In the ABC-partition of an NG-1 graph G, every vertex in B has degree greater than every vertex in A so each vertex in B has a neighbor in C. Thus in our KS partition of G − A, no vertex in K can be moved to S. Hence, α(G − A) = |S| = |C|. Similarly, in the ABC-partition of an NG-2 graph G, every vertex in C has degree less than any vertex in A, so every vertex of C has a non-neighbor in B. Hence in G − A, no vertex in S can be moved to K. Thus, ω(G − A) = |K| = |B|.
For an NG-graph G, let C ′ G be the set of vertices in C G whose neighbor set is all of B G . In the proof of Theorem 28 we obtain our bijections by removing a single vertex from A G .
Proof. Taking graph complements provides a bijection between the classes (N G-1) n and (N G-2) n , so it remains to show there exists a bijection between (N G-1) n and (S) n−1 .
For G ∈ (N G-1) n , choose any w ∈ A G and let f (G) = G − w. We will show that f is our desired bijection. Indeed, we will do more. Partition the set of graphs in (N G-1) n into four classes: (i) those G with |A G | ≥ 3, (ii) those G with |A G | = 2 and C ′ G = ∅, (iii) those G with |A G | = 2 and C ′ G = ∅ and (iv) those G with |A G | = 1. Likewise, partition the set of graphs in (S) n−1 into four classes: We will show that f is a bijection between each of (i), (ii), (iii) and (iv) and its corresponding class (i'), (ii'), (iii'), (iv').
Let G ∈ N G-1 n and let However, each c ∈ C has deg G−w (c) = deg G (c), so some vertices in C may be part of A G−w . We consider the cases mentioned above.
Case (iv): |A| = 1. By Lemma 27, G − A is a split graph on n − 1 vertices with a KS-partition that is both K-max and S-max. By Definition 6, the graph G − A is a balanced split graph, thus G − A ∈ (B) n−1 .
Next, we show the map f is onto by defining its inverse, g. Take any H ∈ (S) n−1 . It is not hard to see that the function g is the inverse to f , thus we have described a bijection between (N G-1) n and (S) n−1 .
Proof. We will demonstrate a bijection between (N G-3) n and (N G-1 − N G-2) n−3 . Then the desired bijection follows because we have already established bijections between the first three classes in row (c) of Table 1 Note that ω(f (G)) = χ(f (G)) = 2 + |B G |. The vertices in f (G) that have degree 1 + |B G | include a 1 and a 2 , and also any vertices in B G that have no neighbors in C G .
Now let H ∈ (N G-1 − N G-2) n−3 with ABC-partition A H ∪ B H ∪ C H and let a 1 , a 2 ∈ A H . We define the map g as follows: g(H) is obtained by adding three vertices y 1 , y 2 , y 3 to H so that H[{a 1 , a 2 , y 1 , y 2 , y 3 }] is a 5-cycle and adding all edges between y 1 , y 2 , y 3  . Finally, the vertices in C H form a stable set and each has at most |B H | neighbors, so these vertices are in C g [H] . Hence the ABC-partition of g(H) is A g(H) = {a 1 , a 2 , y 1 , y 2 , y 3 }, B g(H) = A H − {a 1 , a 2 } ∪ B H , and C g(H) = C H , and g(H) ∈ (N G-3) n . It is straightforward to check that g is the inverse function of f .
For an NG-graph G, let B ′ G be the set of vertices in B G that have no neighbors in C G . In the proof of Theorem 30, we obtain our bijections by removing A G in part (1) and A G ∪ B ′ G in part (2). In both cases, the result is a split graph on n − 2 or fewer vertices. This motivates our defining (T ) ≤n to be the set of split graphs on n or fewer vertices and defining |(S) 0 | = |(T ) ≤0 | = 1. Then by definition, (S) n = (U) n ∪ (B) n and (T ) ≤n = (S) 0 ∪ (S) 1 ∪ (S) 2 ∪ · · · ∪ (S) n .
Theorem 30. Let G be an unlabeled NG-graph on n vertices. Then there are bijections between the following pairs of sets: In the proof of Theorem 30 we used a more complicated bijection in part (2) because the function f (G) = G[B ∪ C] is not injective when applied to graphs in (N G-3) n . This is illustrated in Example 31.
Example 31. Let G be the NG-3 graph where A G = {a 1 , a 2 , a 3 , a 4 , a 5 }, B G = {b 1 , b 2 , b 3 }, C G = {c 1 , c 2 } and b 1 c 1 is the only edge between B G and C G . Note that χ(G) = 6, the vertices in A G have degree 5, those in B G have degree greater than 5, and those in C G have degree less than 5, as needed. The graph G − A G consists of a triangle (with vertices b 1 , b 2  Theorem 26 includes a bijection between the classes (U) n−4 and (T ) ≤n−5 , which implies that |(U) n | = |(T ) ≤n−1 |. We provide a second proof of this equality using the classic presentation of split graphs found in [11] and this second proof does not rely on NG-graphs. Let (U) K n be the set of triples (G, K G , S G ) where G is an unlabeled, unbalanced split graph on n vertices, and K G S G is a KS-partition that is K-max. Similarly, define (U) S n where the KS-partition K G S G is S-max. Recall from Proposition 12 that balanced split graphs have a unique KS-partition, so we may define (B) KS n to be the set of triples (G, K G , S G ) of balanced split graphs on n vertices together with their unique KS-partition.
Create a new graph H consisting of G together with a new vertex w that is adjacent to every vertex in K G . Then H is a split graph and the sets K = K G ∪ {w} and S = S G form a KS-partition of H. Further, H is an unbalanced split graph because w is not adjacent to any vertex in S, Since |(T ) ≤n−1 | = |(T ) ≤n−2 | + |(S) n−1 |, and |U 1 | = 1 = |T 0 |, we see that |(U) n | and |(T ) ≤n−1 | satisfy the same recurrence and initial condition and therefore are equal.

Counting
In this section we use the bijections from Section 4 to calculate the size of classes of split graphs, NG-graphs and pseudo-split graphs. In [6], Clarke gives an expression for the number of minimal k-covers of a set of n indistinguishable objects. Royle [15] then describes a bijection between such k-covers and the set of split graphs on n vertices with exactly k maximal cliques that each contain a vertex in none of the other maximal cliques. Summing over k from 1 to n, Royle obtains a formula for |(S) n |, the number of split graphs on n vertices. Unfortunately, the formula is quite complicated.
Our bijections from Section 4 allow us to calculate the number of balanced and unbalanced split graphs, all categories of NG-graphs and pseudo-split graphs solely in terms of the number of split graphs. Let (PS) n denote the set of pseudo-split graphs on n vertices. The corollary below describes the exact formulas.
Corollary 33. The following equalities hold for each n ≥ 1.   (1), (3) and (4) follow directly from the bijections in Section 4. To prove (2), we use (1) and the fact that a split graph is either balanced or unbalanced, and to prove (5) we apply (1) and (4) and Remark 9. Finally, to prove (6), we use Remark 4 and apply the formula from (4).
Recall that |(T ) ≤n | = n i=0 |(S i )|. In Table 2, we make use of the values computed by Royle [15] for |(S) n | and the formulas in Corollary 33 to determine the values for |(T ) ≤n |, |(U) n |, |(B) n |, |(N G) n | and |(PS) n | for n = 0, . . . , 11. The table in [15] shows rapid growth in the number of split graphs. Royle does not divide split graphs into balanced and unbalanced as we do. Table 3 shows the ratio of the number of balanced split graphs to the number of split graphs on n vertices, indicating that the rapid growth in the number of split graphs comes from the balanced category. We conjecture that this ratio approaches 1 as n goes to infinity. We now show why this may be the case.

Acknowledgments
We would like to thank Ke Chen [4] and David Constantine [8] for their assistance in proving Theorem 34.   Table 3: The ratio of the number of balanced split graphs to split graphs on n vertices.