K-Trees

Why

We generalize trees and discuss an example of chordal graphs.¹

Let $k \in \N $. A $k$-tree is defined indirectly. Let $G = (V, E)$ be a a complete graph and $\nu m{V} = k$.

The complete graph on $ If $ A $k$-tree is an undirected graph with at least $k$ vertices. The only $k$-tree with $k$ vertices is the complete graph.

All $k$-trees are chordal.

Induction on $k$-tree with $k$ vertices.

Future editions will modify, and may introduce $k$-trees without chordal graphs. ↩︎