Край в NetworkX определяется его узлами, поэтому я не совсем уверен, что вы спрашиваете здесь. Конкретное ребро в графе - это просто кортеж узлов с необязательным весом.
import networkx as nx
g = nx.Graph()
g.add_edge(1,2)
g.add_edge(2,3)
g.edges()
дает
[(1, 2), (2, 3)]
Как видите, список ребер явно содержит узлы каждого ребра.
Обновление: Делает ли это то, что вы хотите?
#!/usr/bin/python
import networkx as nx
import random
g = nx.Graph()
g.add_edges_from([(1,2),(2,3),(1,4),(2,5)])
random_edge = random.choice(g.edges())
print 'Randomly selected edge is:', random_edge
print 'Nodes are', random_edge[0], 'and', random_edge[1]