3
$\begingroup$

An edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set. I am interested in finding the minimum edge cover of a tree such that each vertex is incident to an odd number of edges. Is anything similar studied in Computer Science?

$\endgroup$
2
$\begingroup$

There is at most one edge cover which touches each vertex an odd number of times. To see this, let us consider a more general problem, in which each vertex is labeled either "odd" or "even". We want to cover each vertex by an odd or even number of edges, according to its label.

If the tree contains more than one vertex, then we can always find some leaf. It it is labeled "odd", every solution must contain the unique edge containing it. We add this edge to the edge cover, remove the leaf, and modify the label at the other end of the edge accordingly. If the leaf is labeled "even", every solution must not contain the unique edge containing it, and so we simply remove the vertex. Eventually only one vertex will remain. There is a solution if and only if this vertex is labeled "even".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.