A cut is a partition of the vertices of a graph into two disjoint subsets.

The cut-set of the cut is the set of edges whose end points are in different subsets of the partition.

This problem is two parts, the first part (below), I've gotten:

$A \subseteq E(G)$ is even-degree if every vertex of $G$ is incident with an even number of nonloop edges in $A$. Show that if $A$ and $B$ are both even-degree then so is $(A-B)\cup (B-A)$. Deduce that if $T$ is a spanning tree of $G$, there is an even-degree set $A \subseteq E(G)$ with $A \cup E(T) = E(G)$.

The second part :

Show that if $G$ is connected and loopless and $Z \subseteq E(G)$, there is an even-degree set $A \subseteq E(G)$ with $Z \subseteq A$ if and only if there is no cut set $D \subseteq Z$ with $|D|$ odd. (Hint for “if”: use induction on $|Z|$. If there is no cut included in $Z$, show there is a spanning tree $T$ with $Z \subseteq E(G) - E(T)$, and use the above part. If there is a cut included in $Z$, remove one of its elements from $Z$ and use induction).

I'm still confused given the hint. Any help with either direction (if or only if) would be appreciated.


Your Answer

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

Browse other questions tagged or ask your own question.