How many new branches will the complement graph of a deleted edge have?

[evinda]

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]

$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]

$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]

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]

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]

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]

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]

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]

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]

Yes! (Yes) (Sun)

Great! (Happy)

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

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]

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]

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)