A nontrivial tree T of order n has the property that T complement is a maximal p

Question

A nontrivial tree T of order n has the property that T complement is a maximal planar graph.
What is n? and could you try to give me an example of a tree T with this property. It would be great to help me understand the topic.

Explanation / Answer

For a connected graph G of order n > 3 and an ordering (also called a linear ordering) s: v1; v2; : : : ; vn of the vertices of G, the number d(s) is dened as d(s) = n??1 X i=1 d(vi; vi+1): The traceable number t(G) of G is dened by t(G) = min fd(s)g ; where the minimum is taken over all sequences s of the elements of V (G). Thus if G is a connected graph of order n > 2, then t(G) > n ?? 1. Furthermore, t(G) = n ?? 1 if and only if G is traceable. For example, since the graph G of Figure 1 is traceable and has order 5, it follows that t(G) = 4. As with Hamiltonian numbers of graphs, we now see that there is an alternative way to dene the traceable number of a connected graph. Denote the length of a walk W in a graph by L(W).

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.