Tree-decompositions of graphs. I (Q1370176)

The author proves the following two theorems: Theorem 1. Let \(G\) be a connected graph with order \(n\geq 3\) and size \(2n-4\) and \(u\) and \(v\) be two given vertices of \(G\) with \(uv\in E(G)\). Then \(G\) has an \(\{n,n-2\}\)-tree-decomposition with \(u\) and \(v\) as the two singular vertices if and only if the number of edges \(\varepsilon(H)\leq 2(|H|-1)-|H\cap\{u,v\}|\) for any induced subgraph \(H\) of \(G\) with order at least 3. Theorem 2. Let \(G\) be a connected graph with order \(n\geq 3\) and size \(2n-4\) and \(u\) and \(v\) be two given vertices of \(G\). Then \(G\) has an \(\{n-1,n-1\}\)-tree-decomposition with \(u\) and \(v\) as the two singular vertices if and only if \(uv\notin E(G)\) and the number of edges \(\varepsilon(H)\leq 2(|H|- 1)-|H\cap\{u,v\}|\) for any induced subgraph \(H\) of \(G\) with order at least 3.