Is the union of a spanning tree and its complement always a complete graph?

126 Views Asked by At

Consider an undirected graph $G = (V_G, E_G), |V| = n$ . Let $T = (V_T, E_T)$ be a spanning tree of $G$, and let $T^\prime = (V_{T^\prime}, E_{T^\prime})$ be the complement of $T$ such that e $\in$ $E_{T^\prime}$ $\iff$ e $\notin$ $E_T$. Is it always true that $E_{T}$ $\cup$ $E_{T^\prime} = K_n$ ?

I observed that this is indeed the case for G = $K_2, K_3, K_4, K_5$ (trying to solve a problem involving complete graphs), but I wanted to make sure it held in the general case.

1

There are 1 best solutions below

1
On BEST ANSWER

This is trivially the case. Clearly if the union contains all edges in the graph and all edges in the complement, then it is a complete graph because it contains all edges.