Welcome to our community

Be a part of something great, join today!

Number of spanning trees

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,718
Hello!!! (Wave)

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? (Thinking)
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,718
$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? (Thinking)
 

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,679
$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? (Thinking)
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
Apr 13, 2013
3,718
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}$ ? (Thinking)
 

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,679
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}$ ? (Thinking)
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
Apr 13, 2013
3,718
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? (Thinking)
 

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,679
I see... But how do we find then the number of spanning trees? (Thinking)
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
Apr 13, 2013
3,718
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? (Thinking)
 

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,679
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? (Thinking)
Yes! (Yes) (Sun)
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,718
Great!!! (Happy)

Similarly, we get the following graph by extending each vertex of the complete graph $K_7$ with an additional edge.


graph6.JPG

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? (Thinking)
 

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,679
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? (Thinking)
Right again! (Yes) (Sun) (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
Apr 13, 2013
3,718
Right again! (Yes) (Sun) (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!!! (Blush)