Hi.

path = FindPath[g,1,4,Infinity,All]
{{1,2,4},{1,2,3,4}}

rules = PropertyValue[g,EdgeLabels]
{3<->4->D,2<->4->C,1<->2->A,2<->3->B}

EdgeList/@(PathGraph/@path) /.rules
{{A,C},{A,B,D}}

As a side note, notice that you are using variables with a Capital letter for the edge labels. Also notice that in both replies, the solution has the letter C & D in black. The other letters are in light blue. The black letters are built-in functions. If you had a larger graph, you would be using letters like N which is also a built in variable. Did you mean to use Letters? Just an idea with the thought of having a larger graph. You could use Subscript also...etc

g=Graph[{1<->2,2<->3,2<->4,3<->4}];

MyEdges = Thread[Rule[EdgeList[g], CharacterRange["A", "D"]]]

g = SetProperty[g, EdgeLabels -> MyEdges];

Just to be different:

Graph[g, VertexLabels -> Table[i -> Placed["Name", Center], {i, 4}], 
 VertexSize -> 0.1]

HTH Dana (Mathematica 10.2)

This uses your EdgeLabels and the list of paths from your example. Can use adapt this to get what you want?

In[1]:= edgerule = {1 <-> 2 -> A, 2 <-> 3 -> B, 2 <-> 4 -> C, 3 <-> 4 -> D} /. UndirectedEdge -> List; 
Map[Partition[#, 2, 1] &, {{1, 2, 4}, {1, 2, 3, 4}}] /. edgerule

Out[1]= {{A, C}, {A, B, D}}

I have applied your technique to my notebook uploaded. But I am getting combinations of edges and vertices.

Attachments: