How do I get the external face of a planar embedded graph?

edit

First of all I am new to Sage and Python.

I need to get the external face a planar embedding and I immagined that it is always the first element returned by the function faces().

But in this example it seems to change. See the first and the second run.

Is it something about the function faces() or an error in this program?

print ("--- Create a graph")
G = Graph(sparse=True)
G.add_edge(1,2,"1-2")
G.add_edge(2,3,"2-3")
G.add_edge(3,4,"3-4")
G.add_edge(4,5,"4-5")
G.add_edge(5,1,"5-1")
G.add_edge(1,6,"1-6")
G.add_edge(2,10,"2-10")
G.add_edge(3,12,"3-12")
G.add_edge(4,11,"4-11")
G.add_edge(5,7,"5-7")
G.add_edge(6,7,"6-7")
G.add_edge(6,8,"6-8")
G.add_edge(8,10,"8-10")
G.add_edge(10,12,"10-12")
G.add_edge(12,11,"12-11")
G.add_edge(7,9,"7-9")
G.add_edge(8,9,"8-9")
G.add_edge(9,11,"9-11")

print ("--- Embed on a plane")
void = G.layout(layout = "planar", save_pos = True)

G.plot()

# Kempe reduction: for each loop remove an edge from faces <= F5
#
while len(G.faces()) > 2:

    print ("Number of faces: ", len(G.faces()))

    # Remove the external face. Is it always faces[0]???
    #
    faces = G.faces()
    externalFace = faces[0]
    facesWithoutTheExternalFace = copy(faces)
    facesWithoutTheExternalFace.remove(externalFace)
    print ("faces: ", faces)
    print ("externalFace: ", externalFace)
    print ("facesWithoutTheExternalFace: ", facesWithoutTheExternalFace)

    # Find the fist face [0] with len <= 5. It always exists: unavoidable set
    #
    faceToReduce = [x for x in facesWithoutTheExternalFace if len(x) <= 5][0]
    print ("Face <= 5: ", faceToReduce)

    # Find the first edge of the faceToReduce that is not on an edge on the external face
    #
    edgeToRemove = [x for x in faceToReduce if not x in externalFace][0]
    print ("edgeToRemove: ", edgeToRemove)

    verticesToRemove = G.get_vertices(edgeToRemove)
    print ("verticesToRemove ", verticesToRemove)

    G.delete_edge(edgeToRemove)
    neighborsOfTheFirstVertex = G.neighbors(verticesToRemove.keys()[0])
    neighborsOfTheSecondVertex = G.neighbors(verticesToRemove.keys()[1])
    print ("neighborsOfTheFirstVertex = ", neighborsOfTheFirstVertex)
    print ("neighborsOfTheSecondVertex = ", neighborsOfTheSecondVertex)
    G.delete_vertices(verticesToRemove)
    G.add_edge(neighborsOfTheFirstVertex[0], neighborsOfTheFirstVertex[1])
    G.add_edge(neighborsOfTheSecondVertex[0], neighborsOfTheSecondVertex[1])
    G.plot()