There is a fruitful interaction between quantum field theory and enumerative graph theory. In this talk, we introduce half-edge labeled graphs, their automorphism groups, and even/odd orientability. We describe a few enumerative results as well as provide entirely combinatorial proofs of known sign formulas. To conclude, we allude to applications of these results to quantum field theoretic partition functions and generating functions for the Euler characteristic of Kontsevich's graph complex.