# Algoritm to sample an even subgraph of a graph

In some problems related to the Ising model in physics and mathematics the following problem comes up:

Suppose I have a graph $$G$$. Then an even spanning subgraph of $$G$$ is a subgraph where you keep all the vertices and some of the edges such that each vertex has even degree.There is always at least one since the empty spanning subgraph is always even. Now, among all the even spanning subgraphs of $$G$$ I want to sample one uniformly at random.

Is there an fast and preferably easy to implement algoritm to do that?

Is this a well studied problem? If yes: could you point me to some references?

Some background: The space of even spanning subgraphs of a graph has some nice structure since if you have two of them then you can take their symmetric difference and it will still be an even spanning subgraph. This means that it is a vector space of the field $$\mathbb{F}_2$$ and you can pick a basis of that space – in particular this shows that the number of even spanning subgraphs is always a power of 2. I wonder how difficult it is to find the basis elements since if you have some you just flip coins for each and take the symmetric difference of all the graphs where you get head. Another point is that there might be a smart low-tech randomized way to do this.