Maximum properly colored trees in edge-colored graphs

An edge-colored graph G is a graph with an edge coloring. We say G is properly colored if any two adjacent edges of G have distinct colors, and G is rainbow if any two edges of G have distinct colors. For a vertex $$v \in V(G)$$ v ∈ V ( G ) , the color degree $$d_G^{col}(v)$$ d G col ( v ) of v is the number of distinct colors appearing on edges incident with v. The minimum color degree $$\delta ^{col}(G)$$ δ col ( G ) of G is the minimum $$d_G^{col}(v)$$ d G col ( v ) over all vertices $$v \in V(G)$$ v ∈ V ( G ) . In this paper, we study the relation between the order of maximum properly colored tree in G and the minimum color degree $$\delta ^{col}(G)$$ δ col ( G ) of G. We obtain that for an edge-colored connected graph G, the order of maximum properly colored tree is at least $$\min \{|G|, 2\delta ^{col}(G)\}$$ min { | G | , 2 δ col ( G ) } , which generalizes the result of Cheng et al. [Properly colored spanning trees in edge-colored graphs, Discrete Math., 343 (1), 2020]. Moreover, the lower bound $$2\delta ^{col}(G)$$ 2 δ col ( G ) in our result is sharp and we characterize all extremal graphs G with the maximum properly colored tree of order $$2\delta ^{col}(G) \ne |G|$$ 2 δ col ( G ) ≠ | G | .