V we add k - 2 ”buffer vertices”:
v1,…,vk-2 connected only to v. We add a set of buffer vertices for each original
vertex in the graph. Call this new graph G’. Clearly the transformation from G to G’
takes O(n ⋅ (k - 2)) time.
Definition
Given an undirected graph G = (V, E), there exists a spanning tree T in G, in which each node has degree ≤ 2, if such tree exists.
Reduction from Hamiltonian Path from simple case to general case
Given a graph G that contains Hamiltonian Path, we claim that this graph also has Spanning Tree with degree 2.
Claim 4.13.9.1. Hamiltonian Path ≤ p 2-Spanning Tree (Hamiltonian Path is a
special case of 2-Spanning Tree)
Given a graph G that contains Hamiltonian Path if and only if G also has
Spanning Tree with degree 2.
Given a graph G that contains Hamiltonian Path ⇒ G also has Spanning Tree with degree 2.
Proof. Given a Hamiltonian Path of G contains all vertices of G with no cycle and the degree of each vertex on the path is no more than 2. Therefore it is also a 2-Spanning Tree of G. __
G also has Spanning Tree with degree 2 ⇒ Given a graph G that contains Hamiltonian Path.
Proof. Given a 2-Spanning Tree with each vertex in the tree has no more than 2 neighbor nodes, which is exactly the Hamiltonian Path. __
Reduction from 2-Spanning Tree from simple case to general case
Given a graph G = (V,E), at each vertex v V we add k - 2 ”buffer vertices”:
v1,…,vk-2 connected only to v. We add a set of buffer vertices for each original
vertex in the graph. Call this new graph G’. Clearly the transformation from G to G’
takes O(n ⋅ (k - 2)) time.
Claim 4.13.9.2. 2-Spanning Tree ≤p k-Spanning Tree (2-Spanning Tree is a special
case of k-Spanning Tree)
Given a graph G that has a 2-Spanning Tree if and only if G’ has a k-Spanning
Tree, for k > 2.
Given a graph G that has a 2-Spanning Tree ⇒ G’ has a k-Spanning Tree, for k > 2.
Proof. If G has 2-Spanning Tree, then from the construction above, G’ must have k-Spanning Tree, since every vertex in G’ has k vertices (original 2 nodes plus (k-2) buffer nodes). Thus, proved. __
Given a graph G’ has a k-Spanning Tree, for k > 2 ⇒ G that has a 2-Spanning Tree.
Proof. Given a k-spanning tree of G’ must contain all the buffer vertices as leaves, since they all have degree 1. Removing the buffer vertices from the spanning tree gives a 2-spanning tree of G. Thus, proved. __