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

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Trees
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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)
 
Physics news on Phys.org
$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)
 
evinda said:
$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$.
 
Opalg said:
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)
 
evinda said:
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.
 
Opalg said:
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)
 
evinda said:
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.
 
Opalg said:
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)
 
evinda said:
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)
 
  • #10
Opalg said:
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)
 

Attachments

  • graph6.JPG
    graph6.JPG
    4.2 KB · Views: 90
  • #11
evinda said:
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.)
 
  • #12
Opalg said:
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)
 

Similar threads

Replies
4
Views
2K
Replies
2
Views
3K
Replies
1
Views
2K
Replies
22
Views
2K
Replies
4
Views
2K
Replies
2
Views
2K
Replies
2
Views
2K
Replies
1
Views
2K
Back
Top