Edge Elimination Number
APL (77)

{0=⍴,⍵:1⋄C←0/⍨⍴V←∪∊G←⍵⋄0∊C⊣{C[V⍳⍵]:⍬⋄C[V⍳⍵]←1⋄∇¨⍵~⍨∊G/⍨⍵∊¨G}⊃V:0⋄+/∇¨⍵∘~∘⊂¨⍵}


This is a function that takes a list of edges as a graph, i.e.:

      {0=⍴,⍵:1⋄C←0/⍨⍴V←∪∊G←⍵⋄0∊C⊣{C[V⍳⍵]:⍬⋄C[V⍳⍵]←1⋄∇¨⍵~⍨∊G/⍨⍵∊¨G}⊃V:0⋄+/∇¨⍵∘~∘⊂¨⍵} (0 2)(0 3)(1 3)(1 4)(1 5)(2 3)(3 4)(3 5)
16560


(Incidentally, this takes about half a second on my computer.)

So the format is [[v1,v2], [v1,v2], ...]. To pass in a single-edge graph, you need to enclose it first, otherwise you get [0,1] instead of [[0,1]]:

      {0=⍴,⍵:1⋄C←0/⍨⍴V←∪∊G←⍵⋄0∊C⊣{C[V⍳⍵]:⍬⋄C[V⍳⍵]←1⋄∇¨⍵~⍨∊G/⍨⍵∊¨G}⊃V:0⋄+/∇¨⍵∘~∘⊂¨⍵} ⊂0 1
1  


Explanation:


Base case 1 (empty graph):

0=⍴,⍵:1: if the graph is empty, return 1: the current path has emptied the graph while keeping it connected.

Base case 2 (unconnected graph):

C←0/⍨⍴V←∪∊G←⍵: store the list of edges in G, the vertices in V, and a 0 for each vertex in C.
{...}⊃V: See if the graph is connected. Starting with the first vertex:

C[V⍳⍵]:⍬: if the vertex has already been visited, do nothing
C[V⍳⍵]←1: mark the current vertex as visited
G/⍨⍵∊¨G: find each edge this vertex is connected to
⍵~⍨∊: find all vertices involved in those edges, except the current vertex
∇¨: visit all those vertices

0∊C...:0: afterwards, if one of the vertices is not visited, the graph is no longer connected. The current path is invalid, so return 0.

Recursive case:

⍵∘~∘⊂¨⍵: For each edge, create the graph formed by removing that edge, along with any orphaned vertices, from the current graph.
∇¨: For each of those graphs, find its edge elimination number.
+/: Sum those.