1
$\begingroup$

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.

$\endgroup$

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.