# Number of spanning trees

#### evinda

##### Well-known member
MHB Site Helper
Hello!!! Wo consider the graph $G$ that we get by deleting any edge from the complete bipartite graph $K_{7,8}$. How many spanning trees does the complement graph $\overline{G}$ of $G$ have?

Could you give me a hint how we can find the desired number of spanning trees? #### evinda

##### Well-known member
MHB Site Helper
$K_{7,8}$ is a graph which contains $7$ vertices at the one side and $8$ vertices at the other side.
Each vertex of the left side is connected to each vertex of the right side, right?
We get $G$ by deleting one of the edges of the above graph. Right?
So at the complement graph $\overline{G}$ of $G$, is there only the edge that we have deleted in order to create $G$ ? Or am I wrong? #### Opalg

##### MHB Oldtimer
Staff member
$K_{7,8}$ is a graph which contains $7$ vertices at the one side and $8$ vertices at the other side.
Each vertex of the left side is connected to each vertex of the right side, right? Yes.
We get $G$ by deleting one of the edges of the above graph. Right? Yes.
So at the complement graph $\overline{G}$ of $G$, is there only the edge that we have deleted in order to create $G$ ? Or am I wrong? In the graph $G$, there are no edges connecting vertices on the same side. So the $7$ vertices on one side have no connecting edges. Therefore in the complement graph these vertices will all be connected to each other, so they will form a complete $K_7$ graph.

Similarly the $8$ vertices on the other side have no connecting edges in $G$. So the complement graph will convert them into a complete $K_8$.

#### evinda

##### Well-known member
MHB Site Helper
In the graph $G$, there are no edges connecting vertices on the same side. So the $7$ vertices on one side have no connecting edges. Therefore in the complement graph these vertices will all be connected to each other, so they will form a complete $K_7$ graph.

Similarly the $8$ vertices on the other side have no connecting edges in $G$. So the complement graph will convert them into a complete $K_8$.
So the complement graph $\overline{G}$ will have $\frac{7 \cdot 6}{2}+\frac{8 \cdot 7}{2}+1=50$ edges, right?

Since $\overline{G}$ will be connected and it will contain $7+8=15$ vertices, does it hold that the total number of spanning trees will be $15^{13}$ ? #### Opalg

##### MHB Oldtimer
Staff member
So the complement graph $\overline{G}$ will have $\frac{7 \cdot 6}{2}+\frac{8 \cdot 7}{2}+1=50$ edges, right? Yes

Since $\overline{G}$ will be connected and it will contain $7+8=15$ vertices, does it hold that the total number of spanning trees will be $15^{13}$ ? No, that would only happen if $\overline{G}$ was the complete $K_{15}$ graph. In fact, it consists of a $K_7$ and a $K_8$ with a single connecting edge.

#### evinda

##### Well-known member
MHB Site Helper
No, that would only happen if $\overline{G}$ was the complete $K_{15}$ graph. In fact, it consists of a $K_7$ and a $K_8$ with a single connecting edge.
I see... But how do we find then the number of spanning trees? #### Opalg

##### MHB Oldtimer
Staff member
I see... But how do we find then the number of spanning trees? To get a spanning tree for $\overline{G}$ you will need a spanning tree for $K_7$ and a spanning tree for $K_8$. They will then be joined into a single tree by the edge connecting the two parts of the graph.

#### evinda

##### Well-known member
MHB Site Helper
To get a spanning tree for $\overline{G}$ you will need a spanning tree for $K_7$ and a spanning tree for $K_8$. They will then be joined into a single tree by the edge connecting the two parts of the graph.
If a graph is a complete graph with $n$ vertices, then total number of spanning trees is $n^{n-2}$, right?

So the number of spanning trees of $\overline{G}$ will be $7^{5} \cdot 8^{6}$, right? #### Opalg

##### MHB Oldtimer
Staff member
If a graph is a complete graph with $n$ vertices, then total number of spanning trees is $n^{n-2}$, right?

So the number of spanning trees of $\overline{G}$ will be $7^{5} \cdot 8^{6}$, right? Yes!  #### evinda

##### Well-known member
MHB Site Helper
Yes!  Great!!! Similarly, we get the following graph by extending each vertex of the complete graph $K_7$ with an additional edge. The number of spanning trees of $K_7$ is $7^5$ and, with the same logic as above, this will also be the number of spanning trees of the new graph, right? #### Opalg

##### MHB Oldtimer
Staff member
The number of spanning trees of $K_7$ is $7^5$ and, with the same logic as above, this will also be the number of spanning trees of the new graph, right? Right again!  (if you think of it in botanical terms, it's the same tree with a new twig sprouting at the end of each branch.)

#### evinda

##### Well-known member
MHB Site Helper
Right again!  (if you think of it in botanical terms, it's the same tree with a new twig sprouting at the end of each branch.)
Nice... Thank you very much!!! 