Editing Chordal graph (section)

==Intersection graphs of subtrees==
[[Image:Tree decomposition.svg|thumb|A chordal graph with eight vertices, represented as the intersection graph of eight subtrees of a six-node tree.]]
An alternative characterization of chordal graphs, due to {{harvtxt|Gavril|1974}}, involves [[tree (graph theory)|trees]] and their subtrees.

From a collection of subtrees of a tree, one can define a '''subtree graph''', which is an [[intersection graph]] that has one vertex per subtree and an edge connecting any two subtrees that overlap in one or more nodes of the tree. Gavril showed that the subtree graphs are exactly the chordal graphs.

A representation of a chordal graph as an intersection of subtrees forms a [[tree decomposition]] of the graph, with [[treewidth]] equal to one less than the size of the largest clique in the graph; the tree decomposition of any graph ''G'' can be viewed in this way as a representation of ''G'' as a subgraph of a chordal graph. The tree decomposition of a graph is also the junction tree of the [[junction tree algorithm]].