# Revision history [back]

### treewidth()

Hi guys. Is there a bug with the treewidth function? I let G be a tree on 5 nodes and calculate a tree decomposition. However, the answer I get does not seem to be correct as the set of vertices returned are {0},{1},{2,3},{3},{3,4}. The definition of a tree decomposition requires that if (i,j) is an edge in G then there is a bag that contains both i and j. But clearly the above tree decomposition does not have satisfy this property?

 2 No.2 Revision slelievre 12551 ●11 ●121 ●250 http://carva.org/samue...

### treewidth()

Hi guys. Is there a bug with the treewidth function? I let G be a tree on 5 nodes and calculate a tree decomposition. However, the answer I get does not seem to be correct as the set of vertices returned are {0},{1},{2,3},{3},{3,4}. The definition of a tree decomposition requires that if (i,j) is an edge in G then there is a bag that contains both i and j. But clearly the above tree decomposition does not have satisfy this property?

Thank you in advance for your help!To illustrate with a concrete example (not the one above):

M = Matrix([[0, 0, 1, 0, 1],
[0, 0, 1, 0, 0],
[1, 1, 0, 1, 0],
[0, 0, 1, 0, 0],
[1, 0, 0, 0, 0]])
g = Graph(M)
T = g.treewidth(certificate=True)
T.vertices()


This returns:

[{0}, {2}, {2, 3}, {0, 4}, {1, 2}]


Clearly (0,2) is an edge of the original graph but the answer above does not have a bag that contains both 0 and 2.