A note on the existence of an alternating sign on a spanning tree of graphs

Original · EN

For a spanning tree T of a connected graph G and for a labelling ϕ: E(T) → +, -, ϕis called an alternating sign on a spanning tree T of a graph G if for any cotree edge e ∈ E(G)-E(T), the unique path in T joining both end vertices of e has alternating signs. In the present note, we prove that any graph has a spanning tree T and an alternating sign on T.