Allan wrote: << Alternatively, the instance is an (N,N)-bipartite graph, and a solution consists of a degree-1 subgraph (a matching) that includes all the vertices, or the assertion that no such matching exists.

...

This is very close to a problem that came up in my research, which turns out not to be crucial to me, but may be interesting in its own right: Given a graph K with |K| embedded in a orientable surface S, call (S,|K|) a "map" (think geography). Now we define what makes a map a "regular map": Let the connected components of S - |K| be called "faces", the edges of |K| "edges", the vertices of |K| "vertices". Let any triple (v,e,f) of face f that contains edge e that in turn contains vertex v, be called a "flag". It's easy to see that a flag can be used to define an orientation of the surface. An "automorphism" of a regular map is a homeomorphism from S onto itself that carries |K| onto itself. Finally, suppose that any homeomorphism of any flag onto [another flag that defines the same orientation] can be extended to an automorphism of the map to itself. Then (S,|K|) is a "regular map". Examples include all the regular polyhedra (S = S^2), and in fact exist on all compact orientable surfaces. There are 3 well-known geometric examples on the Euclidean plane. And infinitely many on the hyperbolic plane -- with q p-gons around each vertex, whenever (p-2)*(q-2) > 4). (By geometric I mean that the automorphisms of the map are all isometries of S.) Finally, the question: Suppose (S,|K|) is a regular map with either an even number, or infinitely many, vertices. QUESTION: Does there exist a set of edges that contains all vertices exactly once? This is easy to verify for the regular polyhedra, but there doesn't seem to be any obvious pattern. --Dan ________________________________________________________________________________________ "Outside of a dog, a book is man's best friend. Inside of a dog, it's too dark to read." --Groucho Marx