# spanning trees

## Kriesell's Conjecture ★★

Author(s): Kriesell

Conjecture   Let be a graph and let such that for any pair there are edge-disjoint paths from to in . Then contains edge-disjoint trees, each of which contains .

## spanning trees ★★

Author(s):

Problem   Prove or disprove: Let be a graph with the minimum vertex degree at least 2; that is, . Then there exists a spanning tree of such that for every support vertex in if , then .

Keywords: spanning trees

## What is the smallest number of disjoint spanning trees made a graph Hamiltonian ★★

Author(s): Goldengorin

We are given a complete simple undirected weighted graph and its first arbitrary shortest spanning tree . We define the next graph and find on the second arbitrary shortest spanning tree . We continue similarly by finding on , etc. Let k be the smallest number of disjoint shortest spanning trees as defined above and let be the graph obtained as union of all disjoint trees.

Question 1. What is the smallest number of disjoint spanning trees creates a graph containing a Hamiltonian path.

Question 2. What is the smallest number of disjoint spanning trees creates a graph containing a shortest Hamiltonian path?

Questions 3 and 4. Replace in questions 1 and 2 a shortest spanning tree by a 1-tree. What is the smallest number of disjoint 1-trees creates a Hamiltonian graph? What is the smallest number of disjoint 1-trees creates a graph containing a shortest Hamiltonian cycle?

Keywords: 1-trees; cycle; Hamitonian path; spanning trees