Abstract
A graph G = (V,E) is connected if for every pair of vertices u and v in V there is a path from u to v in G; if there isn't, we say that G is disconnected. A graph is kconnected if it has more than k vertices and the removal of any k' < k vertices does not disconnect it.In 1963, Tutte showed that for every 3connected graph G and any pair of vertices u,v in V(G) there is a path P from u to v such that G  V(P) is connected. Based on Tutte's result, in 1975 Lovász conjectured that for every positive integer k there is a positive integer f(k) such that for every f(k)connected graph G and vertices u,v in V(G) there is a path P from u to v where G  V(P) is kconnected. Tutte's result proves that f(1)=3. Based on Lovász conjecture, Fernandes, HernándezVélez, Lee and Pina proposed the study of paths in spanning trees of a graph G that are nonseparating in G. Let G be a graph and T a spanning tree of G. We say that T is a Tutte tree if for any path P in T we have that G  V(P) is connected. Clearly, every Hamiltonian graph has a Tutte tree. In this project, we present the main results about Tutte trees, introduce new results on its existence and propose the study of Tutte trees in hipohamiltonian graphs.In 1984, Itai and Rodeh proposed the concept of independent trees. We say that two trees T' and T'' that are rooted in r are independent if for every vertex x in (V(T') \cap V(T'')) we have that the paths from r to x in T' and T'' are internally disjoint. In 1989, Itai and Zehavi conjectured that for any kconnected graph there are k independent spanning trees rooted on any vertex. This conjecture is known as the Independent Trees Conjecture.Analogously to the concept of independent trees not having paths from the root that share a vertex, Itai and Rodeh proposed edgeindependent trees: trees that are rooted in r and whose paths from the root to any vertex in (V(T') \cap V(T'')) are edgedisjoint. The authors conjectured that for any kedgeconnected graph there are k independent spanning trees rooted on any vertex. This conjecture is known as the EdgeIndependent Trees Conjecture and, although there is no result on its relation to the Independent Trees Conjecture, many of the existing results on edgeindependent trees are clear adaptations from its independent trees counterpart. Both conjectures remain open on cases where k > 4. In this project, we present the main results on Tutte trees and the Independent Trees and EdgeIndependent Trees Conjectures and discourse about the problems we will tackle throughout the project. Besides that, we introduce a new problem on Tutte trees and new results on its existence in graphs. (AU)
