Definition: Graph Decomposable Into \(k\) Trees

Let \(G(V,E,\gamma)\) be a finite undirected graph \(G\) is said to be decomposable into \(k\) trees, if there exist \(k\) subsets of vertices \(V_1,\ldots,V_k\) with the following properties:

A given partition \(V_1,\ldots,V_k\) with these properties is called a tree decomposition of order \(k\). Please note that a graph can have different tree decompositions of the same order.

  1. Definition: Minimal Tree Decomposability

Definitions: 1
Proofs: 2 3 4

Thank you to the contributors under CC BY-SA 4.0!




  1. Piotrowski, Andreas: Own Research, 2014