# 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 .

Keywords: Disjoint paths; edge-connectivity; spanning trees

## 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