  Milgram constructed a 28-vertex cubic graph of genus 4 that disproved Duke's
conjecture relating Betti number to minimum genus. We apply Milgram's method to
construct to find graphs of higher genus violating Duke's conjecture, which
gives a sharper bound on that relationship. These graphs are also
counterexamples to a related conjecture of Nordhaus et al. on the relationship
between minimum and maximum genera of graphs. As a side note, we give a simpler
proof of correctness for Milgram's method and we show that Duke's conjecture is
true for genus at most 3.
