B. =. If and ?. , p}, then delete f ?? in B ?? and add f ?? in B. Then we are in case 1. It can be proved similarly if B = B ?? = {f, f ??

B. =. If and ?. , then the intersection of B and any of its neighbor in T is contained in {p

T. , B. , and B. ??, Then p is contained in all bags on P . Let Y be the neighbor of B on P . If B ? Y = {p, x}, then by definition of the operation Leaf , the tree-decomposition X )) has width at most 3, same size as (T, X ), and B = {f, f ? , p, x} is a leaf. Then deleting x from B we are in case 2. Otherwise, B ? Y = {p}. So {p} separates x from all vertices in B ?? \ {p}. Then all vertices in B ?? \ {p} are children of p and so they are leaves in G. So we can assume that any vertex in B ?? \ {p} are contained only in B ?? (otherwise we can delete it in any other bags) Then delete f, f ? from B and add vertices of B ?? \ {f ?? , p} in B; and make B ?? = {f, f ? , f ??

|. =. Otherwise, In the following, we are going to modify (T, X ) to obtain a tree-decomposition with width at most 3 and size at most s having a bag X containing at least two of f, f ? , f ?? or f ? X and |X| ? 3. Then we are in the above cases. Note that all children of p play the same role (they are all leaves) in G. So it is enough to get that X contains at least two children of p or that X contains one child of p and |X| ? 3

|. ?. Otherwise, |. ?. Since, and |. ?. , If Y has no other child except L in T p , then Y = R since |V (T p )| ? 3. Let X = {p, l} if Y contains no child of p; and X = {p, l, l ? } if Y contains one child l ? of p. Add a new bag Make Z adjacent to all neighbors of Y

A. Proof, S. Corneil, D. G. And-proskurowski, and A. , From Corollary 3, it is enough to prove we can find a 3-potential-leaf in any tree in polynomial time Complexity of finding embeddings in a k-tree, SIAM J. Algebraic Discrete Methods, vol.8, issue.2, pp.277-284, 1987.

A. , S. And-proskurowski, and A. , Characterization and recognition of partial 3-trees, SIAM J. Algebraic Discrete Methods, vol.7, issue.2, pp.305-314, 1986.

B. , H. L. Drange, P. G. Dregi, M. S. Fomin, F. V. Lokshtanov et al., A o(c k n) 5-approximation algorithm for treewidth, p.6321, 2013.

B. , H. L. And-koster, and A. M. , Treewidth computations ii. lower bounds, Inf. Comput, vol.209, issue.7, pp.1103-1119, 2011.

D. , E. D. And-hajiaghayi, and M. , The bidimensionality theory and its algorithmic applications, Comput. J, vol.51, issue.3, pp.292-302, 2008.

D. , D. Kubiak, W. And-zwols, and Y. , Minimum length path decompositions, p.2788, 2013.

G. , M. R. And, J. , and D. S. , Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979.

H. , J. And-tarjan, and R. , Algorithm 447: efficient algorithms for graph manipulation, Commun. ACM, vol.16, issue.6, pp.372-378, 1973.

K. , Y. Ishizuka, A. And-ueno, and S. , Characterization of partial 3-trees in terms of three structures, Graphs and Combinatorics, vol.2, issue.1, pp.233-246, 1986.

M. , J. And-thomas, and R. , Algorithms finding tree-decompositions of graphs, Journal of Algorithms, vol.12, issue.1, pp.1-22, 1991.

R. , N. And-seymour, and P. , Graph minors. II. algorithmic aspects of tree-width, J. Algorithms, vol.7, issue.3, pp.309-322, 1986.

W. , J. A. And-colbourn, and C. J. , Steiner trees, partial 2-trees, and minimum ifi networks, pp.159-167, 1983.