As the title says, what is the correct definition of $k$-tree? There are several papers that talk about $k$-trees and partial $k$-trees as alternative definitions for graphs with bounded treewidth, and I've seen many seemingly incorrect definitions. For example, at least one place defines $k$-trees as follows:

A graph is called a $k$-tree if and only if either $G$ is the complete graph with $k$ vertices, or $G$ has a vertex $v$ with degree $k − 1$ such that $G \setminus v$ is a $k$-tree. A partial $k$-tree is any subgraph of a $k$-tree.

According to this definition, one can create the following graph:

  1. Start with an edge $(v_1, v_2)$, a $2$-tree.
  2. For $i=1\ldots n$, create a vertex $v_i$ and make it adjacent to $v_{i-1}$ and $v_{i-2}$.

Doing this would create a strip of $n$ squares with diagonals. Similarly, we can start creating a band from the first square in a direction orthogonal to the strip above. Then, we would have the first row and first column of an $n \times n$ grid. Filling in the grid is easy by creating vertices and joining them to the vertices to its above and to its left.

The end result is a graph that contains an $n\times n$ grid, which, in effect, is known to be of treewidth $n$.

A correct definition of $k$-trees has to be the following:

A graph is called a $k$-tree if and only if either $G$ is a complete graph with $k$ vertices, or $G$ has a vertex $v$ with degree $k-1$ such that the neighbor of $v$ forms a $k$-clique, and $G \setminus v$ is a $k$-tree.

Then, the grid-like graph described as above cannot be created.

Am I correct?

  • 6
    $\begingroup$ Could you latex-ify your question - makes it easier to read. See meta.cstheory.stackexchange.com/questions/225/… for more details $\endgroup$ Sep 21, 2010 at 8:06
  • $\begingroup$ With this definition ,I can not draw a 2_tree,will you please draw and send it for me? $\endgroup$
    – user32801
    Apr 19, 2015 at 13:06

1 Answer 1


I basically agree with you, with just a tiny modification:

A graph $G$ is a $k$-tree if and only if either $G$ is a complete graph with $k+1$ vertices, or $G$ has a vertex $v$ such that the (open) neighborhood of $v$ forms a $k$-clique, and $G - v$ is a $k$-tree.

In other words, $v$ should have degree $k$, instead $k-1$ in your definition.

I personally prefer the bottom-up definition, but this is just a matter of taste:

  • The complete graph on $k+1$ vertices is a $k$-tree.
  • A $k$-tree $G$ with $n+1$ vertices ($n\ge k+1$) can be constructed from a $k$-tree $H$ with $n$ vertices by adding a vertex adjacent to exactly $k$ vertices that form a $k$-clique in $H$.
  • No other graphs are $k$-trees.

This definition is a slightly modified version of the definition from Pinar Heggernes' lecture notes.

  • $\begingroup$ Yes, my bad for the mistake in $k-1$ degree. (And thanks for the latexing demonstration!) $\endgroup$
    – ethkim
    Sep 21, 2010 at 5:12
  • $\begingroup$ The other difference is the requirement that the neighbourhood be a clique. $\endgroup$ Sep 21, 2010 at 8:37
  • $\begingroup$ @Andras: By "I basically agree with you", I actually meant that I agree that the first definition in the question is incorrect (as it does not require the neighborhood of $v$ to be a clique), and that the second definition in the question is almost correct, as "degree $k-1$" should be replaced with "degree $k$". $\endgroup$ Sep 21, 2010 at 15:34
  • $\begingroup$ Ah, that makes more sense -- thanks for clarifying. $\endgroup$ Sep 21, 2010 at 15:58
  • $\begingroup$ According to your definition, a complete graph on $k$ vertices is a $k$-tree, whose tree-width is $k-1$. However, to the best of my knowledge, a $k$-tree is the maximal graph with tree-width $k$, which implies that a $k$-clique would be a $(k-1)$-tree $\endgroup$
    – Mengfan Ma
    Aug 5, 2019 at 1:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.