Given a trivalent graph embedded in 3-space, we associate to it an instanton homology group, which is a finite-dimensional Z/2 vector space. The main result about the instanton homology is a non-vanishing theorem, proved using techniques from 3-dimensional topology: if the graph is bridgeless, its instanton homology is non-zero. It is not unreasonable to conjecture that, if the graph lies in the plane, the dimension of its instanton homology is equal to the number of Tait colorings of the graph (essentially the same as four-colorings of the planar regions that the graph defines). If the conjecture were to hold, then the non-vanishing theorem for instanton homology would imply the four-color theorem and would provide a human-readable proof.