The Largest Parity Demigenus of a Simple Graph

A graphΓisparity embeddedin a surface if a closed path in the graph is orientation preserving or reversing according as its length is even or odd. Theparity demigenusofΓis the minimum of 2−χ(S) (whereχis Euler characteristic) over all surfacesSin whichΓcan be parity embedded. We calculate the maximum parity demigenus over all loopless graphs of ordern. As a corollary we strengthen the calculation by Jungerman, Stahl, and White of the genus ofKn,nbsp;nwith a perfect matching removed. We conclude by discussing numerous related problems.