Properly colored spanning trees in edge-colored graphs

Abstract A subgraph H of an edge-colored graph G is called a properly colored subgraph if no two adjacent edges of H have the same color, and is called a rainbow subgraph if no two edges of H have the same color. For a vertex v of G , the color degree of v , denoted by d G c ( v ) , is the number of distinct colors appeared in the edges incident with v . Let δ c ( G ) be the minimum value among the color degrees of all the vertices in G . We prove the following two theorems and show that the conditions on the minimum color degree are sharp. Let G be an edge-colored graph. If δ c ( G ) ≥ | G | ∕ 2 , then G has a properly colored spanning tree. Moreover, if δ c ( G ) ≥ | G | ∕ 2 and the set of edges colored with any fixed color forms a subgraph of order at most ( | G | ∕ 2 ) + 1 , then G has a rainbow spanning tree.