<p>I basically agree with you, with just a tiny modification:</p>

<blockquote>
  <p>A graph <span class="math-container">$G$</span> is a <span class="math-container">$k$</span>-tree if and only if either <span class="math-container">$G$</span> is a complete graph with <span class="math-container">$k+1$</span> vertices, or <span class="math-container">$G$</span> has a vertex <span class="math-container">$v$</span> such that the (open) neighborhood of <span class="math-container">$v$</span> forms a <span class="math-container">$k$</span>-clique, and <span class="math-container">$G - v$</span> is a <span class="math-container">$k$</span>-tree.</p>
</blockquote>

<p>In other words, <span class="math-container">$v$</span> should have degree <span class="math-container">$k$</span>, instead <span class="math-container">$k-1$</span> in your definition.</p>

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

<blockquote>
  <ul>
  <li>The complete graph on <span class="math-container">$k+1$</span> vertices is a <span class="math-container">$k$</span>-tree.</li>
  <li>A <span class="math-container">$k$</span>-tree <span class="math-container">$G$</span> with <span class="math-container">$n+1$</span> vertices (<span class="math-container">$n\ge k+1$</span>) can be constructed from a <span class="math-container">$k$</span>-tree <span class="math-container">$H$</span> with <span class="math-container">$n$</span> vertices by adding a vertex adjacent to exactly <span class="math-container">$k$</span> vertices that form a <span class="math-container">$k$</span>-clique in <span class="math-container">$H$</span>.</li>
  <li>No other graphs are <span class="math-container">$k$</span>-trees.</li>
  </ul>
</blockquote>

<p>This definition is a slightly modified version of the definition from <a href="http://www.ii.uib.no/~pinar/chordal.pdf" rel="nofollow noreferrer">Pinar Heggernes' lecture notes</a>.</p>

CC BY-SA 4.0
2019-08-05T01:57:57.187Z
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
Mengfan Ma
CC BY-SA 4.0
2019-11-13T12:34:06.383Z
Indeed, I corrected this to start from the (k+1)-clique as a base case.
Serge Gaspers
CC BY-SA 2.5
2010-09-21T05:12:23.237Z
Yes, my bad for the mistake in $k-1$ degree. (And thanks for the latexing demonstration!)
ethkim
CC BY-SA 2.5
2010-09-21T08:37:25.353Z
The other difference is the requirement that the neighbourhood be a clique.
András Salamon
CC BY-SA 2.5
2010-09-21T15:34:23.950Z
@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$".
Serge Gaspers
CC BY-SA 2.5
2010-09-21T15:58:54.493Z
Ah, that makes more sense -- thanks for clarifying.
András Salamon
CC BY-SA 4.0
2010-09-21T03:45:49.520Z
2019-11-13T12:33:14.617Z
2019-11-13T12:33:14.617Z
Serge Gaspers
<p>As the title says, what is the correct definition of <span class="math-container">$k$</span>-tree? There are several papers that talk about <span class="math-container">$k$</span>-trees and partial <span class="math-container">$k$</span>-trees as alternative definitions for graphs with bounded treewidth, and I've seen many seemingly incorrect definitions. For example, at least one place defines <span class="math-container">$k$</span>-trees as follows:</p>
<blockquote>
<p>A graph  is called a <span class="math-container">$k$</span>-tree if and only if either <span class="math-container">$G$</span> is the complete graph with <span class="math-container">$k$</span> vertices, or <span class="math-container">$G$</span> has a vertex <span class="math-container">$v$</span> with degree <span class="math-container">$k − 1$</span> such that <span class="math-container">$G \setminus v$</span> is a <span class="math-container">$k$</span>-tree. A partial <span class="math-container">$k$</span>-tree is any subgraph of a <span class="math-container">$k$</span>-tree.</p>
</blockquote>
<p>According to this definition, one can create the following graph:</p>
<ol>
<li>Start with an edge <span class="math-container">$(v_1, v_2)$</span>, a <span class="math-container">$2$</span>-tree.</li>
<li>For <span class="math-container">$i=1\ldots n$</span>, create a vertex <span class="math-container">$v_i$</span> and make it adjacent to <span class="math-container">$v_{i-1}$</span> and <span class="math-container">$v_{i-2}$</span>.</li>
</ol>
<p>Doing this would create a strip of <span class="math-container">$n$</span> 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 <span class="math-container">$n \times n$</span> grid. Filling in the grid is easy by creating vertices and joining them to the vertices to its above and to its left.</p>
<p>The end result is a graph that contains an <span class="math-container">$n\times n$</span> grid, which, in effect, is known to be of treewidth <span class="math-container">$n$</span>.</p>
<hr />
<p>A correct definition of <span class="math-container">$k$</span>-trees has to be the following:</p>
<blockquote>
<p>A graph is called a <span class="math-container">$k$</span>-tree if and only if either <span class="math-container">$G$</span> is a complete graph with <span class="math-container">$k$</span> vertices, or <span class="math-container">$G$</span> has a vertex <span class="math-container">$v$</span> with degree <span class="math-container">$k-1$</span> such that the neighbor of <span class="math-container">$v$</span> forms a <span class="math-container">$k$</span>-clique, and <span class="math-container">$G \setminus v$</span> is a <span class="math-container">$k$</span>-tree.</p>
</blockquote>
<p>Then, the grid-like graph described as above cannot be created.</p>
<p>Am I correct?</p>

CC BY-SA 2.5
2010-09-21T08:06:11.767Z
Could you latex-ify your question - makes it easier to read. See http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/237#237 for more details
Suresh Venkat
<graph-theory><treewidth>
What is the correct definition of $k$-tree?
ethkim
# What is the correct definition of $k$-tree?

(Asked by: username_0 on 2010-09-21)

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?

**Tags:** graph-theory, treewidth
> **Comments:**
> **username_1**: Could you latex-ify your question - makes it easier to read. See http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/237#237 for more details  

---

## 1 answers

### Answer by username_2 on 2010-09-21. Score: 17

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](http://www.ii.uib.no/~pinar/chordal.pdf).

> **Comments:**
> **username_0**: Yes, my bad for the mistake in $k-1$ degree. (And thanks for the latexing demonstration!)  
> **username_4**: The other difference is the requirement that the neighbourhood be a clique.  
> **username_2**: @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$".  
> **username_4**: Ah, that makes more sense -- thanks for clarifying.  
> **username_3**: 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  
> **username_2**: Indeed, I corrected this to start from the (k+1)-clique as a base case.  

---

