Elementary Graphs with Respect to f-Parity Factors

This note concerns the f-parity subgraph problem, i.e., we are given an undirected graph G and a positive integer value function f : V(G) -> N, and our goal is to find a spanning subgraph F of G with deg(F) <= f and minimizing the number of vertices x with deg(F)(x) not equivalent to f(x) mod 2. First we prove a Gallai-Edmonds type structure theorem and some other known results on the f-parity subgraph problem, using an easy reduction to the matching problem. Then we use this reduction to investigate barriers and elementary graphs with respect to f-parity factors, where an elementary graph is a graph such that the union of f-parity factors form a connected spanning subgraph.