 # What classes of graphs result from <mover> T <mo accent="false">&#x00AF;<!-- ¯ --> Frederick Kramer 2022-07-11 Answered
What classes of graphs result from $\overline{T}$?
I need help in characterizing the classes of graphs that results from taking the complementary of a tree, i.e., the graph that results from removing the edges of a tree from a complete graph. More formally, let $T=\left(V,E\right)$ be an n-vertex tree with vertex set V and edge set E. Are there known results on the classes of graphs defined by $\overline{T}$?
There are two trivial cases. If $T={S}_{n}$, i.e., is a star tree (one single vertex has degree $n-1$ and the other vertices have degree 1), we have that $\overline{{S}_{n}}=\left\{v\right\}\cup {K}_{n-1}$, i.e., $\overline{{S}_{n}}$ is a graph with an isolate vertex (degree 0) and a $\left(n-1\right)$ vertex clique. I've got the feeling that $\overline{{P}_{n}}$ (where ${P}_{n}$ is an n-vertex path graph) has a precise characterization but I can't put a name to it.
If there are no (or few) results about general T, can we say something about $\overline{T}$ if T belongs to a class of trees, for example caterpillar trees (trees in which the removal of all leaves produces a path graph), lobster trees (trees in which the removal of all leaves produces a caterpillar tree), ...?
Any help will be appreciated. Thank you.
You can still ask an expert for help

## Want to know more about Discrete math?

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it Alexzander Bowman
Explanation:
It is not completely clear what kind of characterization you are looking for. Here's one: complements of trees are the maximal graphs not containing a complete bipartite graph as a spanning subgraph. That is, maximal graphs that do not contain a subgraph of the form ${K}_{s,t}$, where $s+t$ is the number of vertices of the graph. Indeed, a graph is connected if and only if its complement does not contain a subgraph of this form. Since trees are the minimal connected graphs, their complements are the maximal graphs with this property.

We have step-by-step solutions for your answer!