Number of spanning trees in a complete split graph A graph is a complete split graph if we can partition it into an independent vertex set and a clique, such that every vertex of the independent vertex set is adjacent to every vertex in the clique.
How can I count the number of spanning trees in such a graph?
Update:
Using a little bit of sagemath code, I can get the spanning tree count for complete split graphs.
Sage code:
def complete_split_graph(order_of_indep_set, order_of_clique):
    G = graphs.CompleteGraph(order_of_clique)
    clique_vertices = G.vertices()
    for i in range(order_of_indep_set):
        new_vertex = 'i'+str(i)
            for v in clique_vertices:
                G.add_edge(new_vertex, v)
    return G

for i in range(1, 6):
    for c in range(1, 6):
        KS = complete_split_graph(i, c)
        span_tree_count = KS.spanning_trees_count()
        print "$\\tau(\\textrm{{KS}}_{{ {},{} }})$ = {}; ".format(i, c, span_tree_count)

Running the code I get the following results, where $KS_{i, j}$ denotes a complete split graph with an independent set of order $i$ and a clique of order $j$, and $\tau(G)$ denotes the number of spanning trees in a graph $G$:
$\tau(\textrm{KS}_{ 1,1 })$ = 1; 
$\tau(\textrm{KS}_{ 1,2 })$ = 3; 
$\tau(\textrm{KS}_{ 1,3 })$ = 16; 
$\tau(\textrm{KS}_{ 1,4 })$ = 125; 
$\tau(\textrm{KS}_{ 1,5 })$ = 1296; 
$\tau(\textrm{KS}_{ 2,1 })$ = 1; 
$\tau(\textrm{KS}_{ 2,2 })$ = 8; 
$\tau(\textrm{KS}_{ 2,3 })$ = 75; 
$\tau(\textrm{KS}_{ 2,4 })$ = 864; 
$\tau(\textrm{KS}_{ 2,5 })$ = 12005; 
$\tau(\textrm{KS}_{ 3,1 })$ = 1; 
$\tau(\textrm{KS}_{ 3,2 })$ = 20; 
$\tau(\textrm{KS}_{ 3,3 })$ = 324; 
$\tau(\textrm{KS}_{ 3,4 })$ = 5488; 
$\tau(\textrm{KS}_{ 3,5 })$ = 102400; 
$\tau(\textrm{KS}_{ 4,1 })$ = 1; 
$\tau(\textrm{KS}_{ 4,2 })$ = 48; 
$\tau(\textrm{KS}_{ 4,3 })$ = 1323; 
$\tau(\textrm{KS}_{ 4,4 })$ = 32768; 
$\tau(\textrm{KS}_{ 4,5 })$ = 820125; 
$\tau(\textrm{KS}_{ 5,1 })$ = 1; 
$\tau(\textrm{KS}_{ 5,2 })$ = 112; 
$\tau(\textrm{KS}_{ 5,3 })$ = 5184; 
$\tau(\textrm{KS}_{ 5,4 })$ = 186624; 
$\tau(\textrm{KS}_{ 5,5 })$ = 6250000;
However, I am not satisfied with my way of doing it. I would prefer to find a formula, and I'd like to know how to do it without a computer doing the work for me. So I'd appreciate further hints and help.
 A: An alternative would be to use Prufer sequences. (If you don't know what these are, I suggest you look them up, and how they can be used to prove Cayley's formula before reading the rest of this hint).
Write $A$ for the largest independent set in the split graph, and $B$ for the vertex set of the largest clique. Consider the following algorithm for converting a spanning tree in the split graph into two strings, $s_A$ and $s_B$. At step i, pick the leaf with the smallest label. If this leaf is in $A$, append the label of its neighbour to $s_A$. Otherwise, append the label of its neighbour to $s_B$. Delete this leaf from the tree, and repeat until there are only 2 vertices. Can you choose the enumeration of vertices such that you are guaranteed that one of these vertices is in $A$? How long will $s_A$ and $s_B$ be in this process, and what are the possiblities for each? Now come up with a reverse process to convert between 'allowed string pairs' and spanning trees.
This method should give you a nice one term formula for the number of spanning trees.
