Spanning Trees of Dual Graphs
NORMAN BIGGS
Royal Holloway College, University of London, England
Communicated by J. W. T. Youngs
Received May 23, 1969
It is a well-known result that if G and G* are dual planar graphs and T is a spanning tree for G,
then the complement of the edges dual to T is a spanning tree for G*.
The purpose of this note is to show how ideas of Edmonds
, Gustin [2], and Youngs [3]
can be used to formulate precisely the generalization of this result to graphs imbedded in any orientable surface.
In the course of the work several new interpretations of standard graph-theory concepts will be
presented.
1. DUALITY
In the usual sense, an undirected linear graph consists of a set V of
vertices and a set E of edges together with a mapping which assigns to
each edge an unordered pair of vertices. This formulation is difficult to
handle in abstract terms, and so we us
the following notion.
DEFINITION 1. A graph is an ordered quadruple (E, V, h, T) where E
and V are sets (finite for our purposes), X: E + V is a surjection, and
r: E---f E an involution.
Intuitively, E consists of the edges taken twice, once in each direction,
V is the vertex set, h assigns to each directed edge its initial vertex, and T
reverses directions. Thus hi assigns to each directed edge its final vertex,
and an edge e E E for which e = T(e) will be called a loop.
Now if a graph (in the geometric sense) is imbedded in a closed
orientable 2-manifold, then the orientation at each vertex determines
a cyclic permutation of the incident edges; conversely, given such a set
of cyclic permutations we can construct such a 2-manifold in which the
graph is imbedded, following Edmonds [l]. Accordingly we introduce
this idea formally. (Throughout this note, ~$3 denotes the composite
x2 Y2 2.) 
ขอความกรุณาแปลให้หน่อยครับ เป็นเรื่องทบ.กราฟ
NORMAN BIGGS
Royal Holloway College, University of London, England
Communicated by J. W. T. Youngs
Received May 23, 1969
It is a well-known result that if G and G* are dual planar graphs and T is a spanning tree for G,
then the complement of the edges dual to T is a spanning tree for G*.
The purpose of this note is to show how ideas of Edmonds , Gustin [2], and Youngs [3]
can be used to formulate precisely the generalization of this result to graphs imbedded in any orientable surface.
In the course of the work several new interpretations of standard graph-theory concepts will be
presented.
1. DUALITY
In the usual sense, an undirected linear graph consists of a set V of
vertices and a set E of edges together with a mapping which assigns to
each edge an unordered pair of vertices. This formulation is difficult to
handle in abstract terms, and so we us
DEFINITION 1. A graph is an ordered quadruple (E, V, h, T) where E
and V are sets (finite for our purposes), X: E + V is a surjection, and
r: E---f E an involution.
Intuitively, E consists of the edges taken twice, once in each direction,
V is the vertex set, h assigns to each directed edge its initial vertex, and T
reverses directions. Thus hi assigns to each directed edge its final vertex,
and an edge e E E for which e = T(e) will be called a loop.
Now if a graph (in the geometric sense) is imbedded in a closed
orientable 2-manifold, then the orientation at each vertex determines
a cyclic permutation of the incident edges; conversely, given such a set
of cyclic permutations we can construct such a 2-manifold in which the
graph is imbedded, following Edmonds [l]. Accordingly we introduce
this idea formally. (Throughout this note, ~$3 denotes the composite
x2 Y2 2.)