\documentclass[12pt]{article} \usepackage{e-jc} \specs{P50}{20(2)}{2013} \usepackage{amsthm,amsmath,amssymb} \usepackage{latexsym} \newtheorem{thm}{Theorem}[section] \newtheorem{lem}{Lemma}[section] \newtheorem{cor}{Corollary}[section] \newtheorem{prop}{Proposition}[section] \newtheorem{exam}{Example}[section] \newcommand{\ebox}{\ $\Box$\vspace{1ex}} \newcommand{\pr}{{\bf Proof.}\ } \newcommand{\bt}{\begin{thm}} \newcommand{\et}{\end{thm}} \newcommand{\bl}{\begin{lem}} \newcommand{\el}{\end{lem}} \newcommand{\bp}{\begin{prop}} \newcommand{\ep}{\end{prop}} \newcommand{\bc}{\begin{cor}} \newcommand{\ec}{\end{cor}} \newcommand{\bx}{\begin{exam}} \newcommand{\ex}{\end{exam}} \newcommand{\be}{\begin{eqnarray}} \newcommand{\ee}{\end{eqnarray}} \newcommand{\bi}{\begin{itemize}} \newcommand{\ei}{\end{itemize}} \newcommand{\beq}{\begin{equation}} \newcommand{\eeq}{\end{equation}} \newcommand{\veps}{\varepsilon} \newcommand{\noi}{\noindent} \newcommand{\cl}{\centerline} \begin{document} \title{%\vspace{-1.9cm} \bf Distinguishing Maps II: General Case} \date{\dateline{Dec 12, 2011}{May 29, 2013}{Jun 7, 2013}} \author{Thomas W. Tucker\\ \small Department of Mathematics \\[-0.8ex] \small Colgate University \\[-0.8ex] \small Hamilton, NY, U.S.A.\\ } \maketitle \begin{abstract} A group $A$ acting faithfully on a set $X$ has distinguishing number $k$, written $D(A,X)=k$, if there is a coloring of the elements of $X$ with $k$ colors such that no nonidentity element of $A$ is color-preserving, and no such coloring with fewer than $k$ colors exists. Given a map $M$ with vertex set $V$ and automorphism group $Aut(M)$, let $D(M)=D(Aut(M),V)$. If $M$ is orientable, let $D^+(M)=D(Aut^+(M),V)$, where $Aut^+(M)$ is the group of orientation-preserving automorphisms. In a previous paper, the author showed there are four maps $M$ with $D^+(M)>2$. In this paper, a complete classification is given for the graphs underlying maps with $D(M)>2$. There are $31$ such graphs, $22$ having no vertices of valence $1$ or $2$, and all have at most $10$ vertices. \end{abstract} \medskip \section{Introduction}\label{intro} A group $A$ acting faithfully on a set $X$ has {\em distinguishing number} $k$, written $D(A,X)=k$, if there is a coloring of the elements of $X$ with $k$ colors such that no nonidentity element of $A$ is color-preserving, and no such coloring exists with fewer than $k$ colors. The concept was introduced by Albertson and Collins \cite{AC1} in the context of the automorphism group of a graph acting on the vertex set. It originates in the observation that to destroy any symmetry of a necklace of $n$ beads, one needs beads of three different colors for $n=3,4,5$, but only two colors for $n>5$; this observation actually plays a role in some of our proofs. In \cite{TT}, we considered a variety of questions where $X$ is the vertex set of a map $M$ and $A$ is either the full automorphism group $Aut(M)$ for the map, or the orientation-preserving automorphism group $Aut^+(M)$, with respective distinguishing numbers $D(M)$ and $D^+(M)$. In particular, we showed that there are only four maps with $D^+(M)>2$. We also showed there are only finitely many maps with $D(M)>2$ and considered a number of questions for distinguishing chromatic numbers, where vertex colorings are required to be proper. In this paper, we consider the general case of non-orientable maps and orientation-reversing actions on oriented maps. We find the possible underlying graph $G$ for any map $M$ with $D(M)>2$ and for each such graph, we give an example of a map $M$ with underlying graph $G$ and $D(M)>2$. Unlike \cite{TT}, our list of possible underlying graphs is rather long and complicated, although no graph has more than $10$ vertices. This paper is self-contained in terminology, definitions, and methods, but the reader might want to see \cite{TT} for a broader discussion of distinguishability and maps, including a much more extensive list of references. Much of this classification appears in an earlier unpublished preprint (2005). A recent paper by Negami \cite{N} gives a partial classification and relates it to the earlier preprint. We discuss Negami's results at the end of the paper. \smallskip This paper is organized as follows. Section 2 gives definitions, terminology, and some background for maps and their automorphisms, including Petrie duality, reflexible and chiral regular maps, and Cayley maps. In Section 3, we give examples of vertex-transitive and intransitive maps with $D(M)>2$. In Section 4 we give a statement of the classification theorem for maps $M$ with $D(M)>2$. In Section 4, we prove the classification theorem for the intransitive case. In Section 5, we prove the theorem in the case of regular (reflexible) maps. In Section 6, we complete the proof of the classification theorem for transitive maps using overlays of regular reflexible and chiral maps. We note that the concept of distinguishability has forced us to develop a variety of new techniques: partial Petrie duality, $\tau$-edges, induced embeddings for subgraphs, overlays, and angle measure. These in turn have led to a much deeper understanding of the symmetries of a map. In particular, angle measure yields an astonishingly simple and short proof that there are no reflexible regular maps with underlying graph $K_n, n\neq 2,3,4,6$, a well-known result obtained at some length by algebraic methods. Angle measure might hint at a geometric explanation of our results depending on the euclidean or hyperbolic structure carried by maps. Distinguishability has also led us to a variety of small maps, some familiar and some not, many with remarkable symmetry properties. \smallskip \section{Maps, automorphisms, and stabilizers} All our graphs are finite and connected with no multiple edges or loops. A {\em map} $M$ is an embedding of a graph $G$, called the {\em underlying} graph, in a closed surface $S$, called the {\em underlying surface}, such that each component, or {\em face}, of $S-G$ is homeomorphic to an open disc (that is, the embedding is cellular). There are a variety of ways of looking at maps as combinatorial structures: rotation systems or band decompositions \cite{GT}, permutation groups acting on directed edges (monodromy or dart groups)\cite{RSJTW}, triples of vertex-edge-face incidences (flags) \cite{ST}. The rotation viewpoint, being more intuitive and geometric, serves our purposes best. An oriented map naturally defines a cyclic ordering of the directed edges beginning at each vertex, usually called the {\em rotation} at that vertex; the set of all such rotations is called a {\em rotation system} and can be written as a single permutation of the directed edge set whose cycles correspond to vertices. Conversely, given a rotation system, one can construct an oriented map by first assigning to each vertex an oriented disk containing a vertex at the center and spokes for edge-ends in the cyclic order given by the rotation system. Then one can join the vertex-disks by edge-bands to form a compact orientable surface with a number of boundary components, a ``thickening" of the underlying graph. Finally, one can paste disks to the boundary components to form the faces of a map in a closed orientable surface. The faces can be traced out beginning at any directed edge simply by using the rotation at each vertex to choose the next directed edge in the face. For non-orientable maps, there are two possible cyclic orderings at a vertex, since there is no orientation present to differentiate ``clockwise" from ``counterclockwise". We also must specify whether each edge is ``flat" or ``twisted", depending on whether or not the edge-band can be oriented consistently with its end-point vertex-disks. The collection of rotations and twisting, we call a {\em general rotation system}. Notice that one can always reverse the rotation at a vertex in exchange for reversing the twisting of all edges incident to the vertex, twisted to flat and flat to twisted; one can use this operation to define an equivalence relation on general rotation systems. Every embedding defines an equivalence class of general rotation systems and every such equivalence class defines an embedding. It can be shown that a general rotation system defines an orientable embedding if and only if every cycle in the graph contains an even number of twisted edges, or equivalently, if and only if there is an equivalent general rotation system for which all edges are flat. Faces are traced out using the rotation for directions at each vertex, but now if $uv$ is twisted we use at $v$ the reverse of what we use at $u$, and if $uv$ is flat we use the same. Given a general rotation system for the graph $G$, if $H$ is a subgraph of $G$, we can talk about the general rotation system restricted to $H$, where the cyclic order at a vertex of $H$ is simply the original cyclic order, leaving out all the edges not in $H$. Thus for any map with underlying graph $G$, there is an {\em induced} map for any subgraph $H$ of $G$. Note, however, that the underlying surface for the induced map may be different. Given a map $M$, the map obtained by changing all twisted edges to flat and all flat edges to twisted is called the {\em Petrie dual}, denoted $M^P$; see \cite{ST} for a definition in terms of monodromy groups and flags. The underlying graph for $M^P$ is the same as that for $M$, but the faces now correspond to Petrie ``right-left" cycles from the original map $M$. If $M$ is oriented, then $M^P$ is orientable if and only if the underlying graph is bipartite. An automorphism of a map is an automorphism of the underlying graph that extends (as a homeomorphism of the graph) to a homeomorphism of the surface. In terms of general rotation systems, a map automorphism is an automorphism of the underlying graph that, for some general rotation system of the map, either preserves the rotation at every vertex or reverses the rotation at every vertex and that takes flat edges to flat edges and twisted edges to twisted edges. The set of all automorphisms of a map $M$ forms a group, denoted $Aut(M)$; if the map is orientable, the set of all orientation-preserving automorphisms forms a subgroup of index at most $2$ in $Aut(M)$ and is denoted $Aut^+(M)$. The {\em distinguishing number of a map} $M$ with vertex set $V$ is $D(Aut(M),V)$ and is denoted simply $D(M)$; if $M$ is orientable, the {\em orientable distinguishing number}, is $D(Aut^+(M),V)$, denoted simply $D^+(M)$. From our definition of automorphism, it follows that for the Petrie dual $M^P$, the action of $Aut(M)$ and $Aut^P(M)$ on the underlying graph are the same. Indeed, this is true even for a {\em partial Petrie dual} obtained by only changing edge-types in a single edge orbit of $Aut(M)$. In fact, if $B$ is a subgroup of $Aut(M)$, we can also change edge-types only in a single edge orbit of $B$. The resulting map $M'$ will have the same underlying graph $G$ and $Aut(M')$ will contain a subgroup acting on $G$ in the same way as $B$. Given an action of the group $A$ on the set $X$, and given a subset $Y$ of $X$, the {\em set-wise stabilizer} of $Y$ is the subgroup of $a$ in $A$ with $a(Y)=Y$. Although this is usually denoted $A_{\{Y\}}$, we will maintain the notation $Stab(Y)$ used in \cite{TT}. The {\em point-wise stabilizer} is the subgroup of all $a$ such that $a(y)=y$ for all $y$ in $Y$. Again, we use the notation $Fix(Y)$ from \cite{TT} rather than the usual $A_Y$. We say that $Stab(Y)$ or $Fix(Y)$ is trivial if it contains only the identity. The actions in this paper are all faithful, that is for $A$ acting on $X$, $Fix(X)$ is trivial. \smallskip {\em Remarks:} Note that $D(A,X)=1$ if and only if $A$ is the trivial group, and $D(A,X)=2$ if and only if $A$ is nontrivial but $Stab(Y)$ is trivial for some nonempty subset $Y$ of $X$: simply color $Y$ white and all all other elements of $X$ black. Also, if $Fix(Y)$ is trivial and $Y$ has $k$ elements, then $D(A,X) \leq k+1$: just color each element of $Y$ with the first $k$ different colors and color the remaining vertices with the last color. Finally, any faithful action of $A=Z_2\times Z_2$ on a set $X$ has $D(A,X)=2$: color one element of each orbit black and the rest white. \smallskip Unlike graphs, maps have highly restricted set stabilizers. In particular, if $uv$ is an edge, $Fix(u,v)$ has at most one nontrivial element, namely a reflection, which we denote $\tau_{uv}$, that interchanges the faces incident to $uv$. If the map is oriented, then $\tau_{uv}$ is orientation-reversing. Summarizing: \bp If $uv$ is an edge in map $M$, then $Stab(u,v)$ is a subgroup of $Z_2\times Z_2$. If $v$ is a vertex in $M$ of valence $d$, then $Stab(v)$ is a subgroup of the dihedral group $D_d$, acting in the natural way on the cyclic order of vertices adjacent to $v$ given by a rotation for $M$. \ep We call a map {\em all-$\tau$} if every edge $uv$ has the reflection $\tau_{uv}$, {\em no-$\tau$} if none do, and {\em mixed} if some do and some don't. A {\em regular} map $M$ is one with maximal symmetry, that is, vertex-transitive with vertex stabilizer $D_d$. In particular, a regular map is all-$\tau$; note, however, that a vertex-transitive all-$\tau$ map is not necessarily regular. An oriented map $M$ is {\em chiral regular} if $Aut^+(M)$ is transitive on directed edges, so that $M$ is vertex-transitive with cyclic vertex stabilizers of order $d$, but no orientation-reversing automorphism. In particular, a chiral regular map is no-$\tau$. An oriented regular map is also sometimes called {\em reflexible} regular. If $uv$ and $vw$ are edges of map $M$, we call $uvw$ an {\em angle}. An angle $uvw$ is a {\em corner} if $u$ and $w$ are consecutive in the rotation at $v$. If $v$ has valence $d$, the {\em measure} of angle $uvw$ is the number $m\leq d/2$ of corners between $u$ and $w$ in the rotation at $v$; notice that angles are not oriented, with a first and second side, so angle measure is independent of the local orientation for the rotation at $v$. We call an angle {\em straight} if its measure is $d/2$ and {\em bent} otherwise. An angle $uvw$ is {\em closed} if there is an edge $uw$ and {\em open} otherwise. We note that if angle $uvw$ is open, then any element of $Stab(u,v,w)$ fixes $v$. By the dihedral action of $Stab(v)$ on the neighbors of $v$, there is at most one automorphism fixing $v$ and interchanging neighbors $u$ and $w$, called an {\em angle reflection}. We summarize facts about angle stabilizers: \bp Given a bent angle $uvw$, then $Fix(u,v,w)$ is trivial. In particular, if $uvw$ is open, $|Stab(u,v,w)|\leq 2$. If $uvw$ is instead straight, then $|Fix(u,v,w)|=|Fix(u,v)|\leq 2$. In particular, if $uvw$ is open, then $Stab(u,v,w)$ is a subgroup of $Z_2\times Z_2$. \ep We will need to describe some fairly complicated small maps. The easiest way to do this is with Cayley maps \cite{RSJTW, ST}. Given a group $A$ with generating set $S$, the associated {\em Cayley graph} $C(A,S)$ is the directed, labeled graph with vertex set $A$ and directed edge labeled $s$ from $a$ to $as$ for each $a\in A$ and $s \in S$. Left multiplication by $A$ of vertex labels gives a regular (transitive and free) action of $A$ by automorphisms of the graph $C(A,S)$. If we also assign a cyclic order $\rho$ to the elements of $S\cup S^{-1}$, the associated {\em Cayley map} $CM(A,\rho)$ is the oriented map with underlying graph $C(A,S)$ and vertex rotations given by $\rho$. Again, left multiplication by $A$ gives a regular action by map automorphisms. In addition to the natural regular action of $A$ on $CM(A,\rho)$ there may be other symmetries fixing a vertex. In particular, if $f$ is an automorphism of $A$ with $f(\rho(s))=\rho(f(s))$ for all $s\in S$ (i.e. $f$ ``respects" the rotation), then $f$ also defines an orientation-preserving automorphism of the map $CM(A,\rho)$, fixing the identity vertex. If instead $f(\rho(s))=\rho^{-1}(f(s))$ for all $s\in S$ (i.e. $f$ ``reverses" the rotation), then $f$ defines an orientation-reversing automorphism of the map $CM(A,\rho)$, fixing the identity vertex. A Cayley map $CM(A,\rho)$ is {\em balanced} if $\rho(s^{-1})=\rho(s)^{-1}$, for all $s\in S$; that is, if $s\neq s^{-1}$, then they are antipodal in the rotation. Note this implies that if one element of $X$ is an involution, then all are. The natural action of $A$ on $CM(A,\rho)$, as a subgroup of $Aut(CM(A,\rho))$, is normal if and only if $CM(A,\rho)$ is balanced \cite{ST}. In the case where the elements of $S$ are $d$ non-involutions, we give only the first half of the cycle for $\rho$ and abbreviate $(s_1,\cdots,s_d)^b=(s_1, \dots,s_d, s_1^{-1},\dots,s_d^{-1})$. Our graph notation and terminology are as follows. If the graph $G$ has edge $uv$, then we say $u$ and $v$ are {\em adjacent} or $u$ and $v$ are {\em neighbors}. The subgraph of $G$ induced by all the neighbors of $u$ is the {\em link} of $v$, denoted $Link(u)$. The {\em distance} between vertices $u$ and $v$ is the length of the shortest path between them. The {\em diameter} of $G$ is the greatest distance between any two vertices. The complete graph on $n$ vertices is denoted $K_n$, the complete bipartite graph on $m$ and $n$ vertices is $K_{m,n}$, the cycle of length $n$ is $C_n$, and the graph obtained from $K_{2n}$, for $n>1$, by removing $n$ disjoint edges is the octahedral graph $O_{2n}$ (note $O_4=C_4$) The graph obtained by adding $k$ independent vertices to $G$ and joining them by edges to all vertices of $G$ is the {\em $k$-fold suspension} of $G$ and denoted $S_k(G)$. Note that $S_1(K_n)=K_{n+1}$ and $S_2(O_{2n})=O_{2n+2}$. Alternatively, $S_k(G)$ can be written as the join $\bar K_k * G$ of $G$ with the complement of $K_k$. For groups, we let $Z_n$ denote the cyclic group of order $n$ and $D_n$ the dihedral group of order $2n$. The direct product $A\times A\times \cdots \times A$ of $k$ copies of the group $A$ is denoted $A^k$. \section{Examples of maps with $\boldsymbol{D(M)>2}$} We begin by giving two examples to illustrate the role of Petrie duality. \bx Let $M$ the map on the sphere obtained by joining an $m$-cycle, $m=3,4,5$, along the equator with the north and south poles; its underlying graph is $S_2(C_m)$. The action of the dihedral group $B=D_m$ on this map, leaving fixed the north and south poles, has distinguishing number $3$, by the original necklace problem. The action of $B$ has three edge orbits, so we can take a variety of partial Petrie duals with respect to $B$, one of which will be the Petrie dual. Each of these maps has $D(M)=3$. \ex \bx Let $M$ be the tetrahedron. Its Petrie dual $M^P$ has three faces, all of size $4$ and is a map in the projective plane, since the Euler characteristic is $4-6+3=1$. Notice that for any vertices $u,v,w$, each of $uvw$,$vwu$, and $wuv$ is a corner of the map and $Stab(u,v,w)=D_3$. One might expect, as in the orientable case, that this means there is a triangular face of the embedding whose boundary is the $3$-cycle $uvw$. But the embedding has no triangular faces. In addition, we can place a new vertex inside each face and join to the original four vertices to get a map $M$ with underlying graph $S_3(K_4)$ and $D(M)=3$. \ex The following example has underlying graph $K_{m,n}$. \bx Consider the Cayley map $M(m,n)=CM(A, (x,x^{-1},y, y^{-1}))$, where $A=Z_m \times Z_n$ generated by $x,y$ of order $m,n$. Each face of the map is bounded by a cycle in the Cayley graph corresponding to $x^m=1, y^n=1$ or $(xy)^{lcm(m,n)}=1$. Let $B(m,n)$ be the map obtained by placing a new vertex at the center of each of the faces corresponding to $x^m=1$ or $y^n=1$ and then joining the new vertices by edges through the vertices of the original graph $M(m,n)$ (and discarding all the original vertices and edges). This makes $M(m,n)$ the medial graph of $B(m,n)$ \cite{ST}. The graph underlying $B(m,n)$ is $K_{m,n}$. In $M(m,n)$, the stabilizer of the face $F$ corresponding to $x^m=1$ is $D_m$: multiplication by $x$ is a map automorphism rotating $F$ and the group automorphism inverting both $x$ and $y$ reverses the rotation providing a map automorphism reflecting $F$. Similarly, the stabilizer of a $y^n=1$ face is $D_n$. Thus vertex stabilizers in $B(m,n)$ are $D_m$ or $D_n$. In addition, if $m=n$, then the group automorphism interchanging $x$ and $y$ is also a map automorphism for $M(n,n)$, making $B(n,n)$ vertex-transitive. \ex \smallskip We now give examples of maps $M$ with $D(M)=3$. First, we have: \bt \label{valence}\cite{TT} If $M$ has a vertex of valence $1$ or $2$ and $D(M)>2$, then the underlying graph is $C_n, K_{1,n}$ or $K_{2,n}$, for $n=3,4,5$. \et \bt \label{D+}\cite{TT} If $M$ has a no-$\tau$ group action $A$ with $D(A,V)=3$ and all vertices of valence $d>2$, then the underlying graph is $K_4, K_5, K_7, O_6$ or $O_8$. \et The following table provides examples of vertex-transitive, oriented maps $M$ with $D(M)=3, D^+(M)=2$, and no vertices of valence $1$ or $2$. Here $G$ stands for the underlying graph, $d$ for valence, $Stab$ for vertex stabilizer, $g$ for genus. The type of each map is regular (``reg"), not regular but all-$\tau$ (``all"), no-$\tau$ (``no") or mixed (``mix"). \begin{center} \begin{tabular}{|l|c|c|c|c|c|l|} \hline ID & Name & $G$ & $d$ & $Stab$ & $g$ & Type \\ \hline\hline T1 & $CM(Z_4, (1,-1,2))$ & $K_4$ & $3$ & $D_1$ & $1$ & mix \\ \hline T2 & $CM(Z_5, (1,-1,2,-2))$ & $K_5$ & $4$ & $D_1$ & $2$ & no \\ \hline T3 & $CM(Z_2^3, (x,y,z))$ & cube & $3$ & $D_3$& $1$ & reg \\ \hline T4 & $CM(Z_2^3, (x,x+y,y,y+z,\dots))$ & $O_8$ & $6$ & $D_3$ & $7$ & all \\ \hline T5 & $CM(Q, (i,j,k)^b)$ & $O_8$ & $6$ & $D_3$ & $5$ & no \\ \hline T6 & $CM(Z_3^2, (x,y)^b)$ & $C_3\times C_3$ & $4$ & $D_4$ & $1$ & reg \\ \hline T7 & $CM(Z_3^2, (x,y, -x+y)^b)$ & $K_{3,3,3}$ & $6$ & $D_6$ & $1$ & reg \\ \hline T8 & $CM(Z_3^2, (x,x+y,y,y-x)^b)$ & $K_9$ & $8$ & $D_4$ & $10$ & all \\ \hline T9 & $B(3,3)$ & $K_{3,3}$ & $3$ & $D_3$ & $1$ & reg \\ \hline T10 & $B(4,4)$ & $K_{4,4}$ & $4$ & $D_4$ & $3$ & reg \\ \hline T11 & $B(5,5)$ & $K_{5,5}$ & $5$ & $D_5$ & $6$ & reg \\ \hline \end{tabular} \\ \vskip 16 pt {\bf Table 1}: Vertex-transitive maps with $D(M)=3$ but $D^+(M)=2$. \end{center} The proofs that each of these maps have $D(M)>2$, that is $Stab(Y)$ is nontrivial for any set $Y$ of vertices, we leave to the reader; only when $|Y|=4,5$ is there much to check. We note that maps $T1, T2$ are just the necklace problem for $D_4$ and $D_5$. The cube T3 is well-known \cite{AC1}. The action of $Aut(T4)$ on its vertex set is the same as that of $Aut(T3)$. T5 is discussed in \cite{TT}. The action of $Aut(T8)$ on its vertex set is the same as that of $Aut(T6)$. The maps T9-T11 are variations of the necklace problem. We have not given the group structure of $Aut(M)$ for each of the maps in Table 1. Since all the maps except T9-T11 are balanced Cayley maps for some group $A$, making $A$ normal, $Aut(M)$ is a semi-direct product of $A$ with $Stab(v)$. The action of $Stab(v)$ by conjugation on $A$ can be inferred from $Stab(v)$, the presence of $\tau$ edges, and the given generating set for $A$. For example, for map T5, since $Stab(v)=D_3$ and there are no $\tau$ edges, there must be only corner reflections. Thus a typical involution in $Stab(v)$ must be a group automorphism of the quaternions interchanging $i$ and $j$, and interchanging $k$ and $-k$. As another example, for T7, the reflection fixing edges labeled $x$ is the group automorphism $f(x)=x, f(y)=-y$. The groups in T9-T11 are best understood in terms of the original Cayley map $CM(Z_m\times Z_m, (x,y,-x,-y))$, which is the semi-direct product of $Z_m \times Z_n$ by $D_2$ generated by the group automorphism inverting $x$ and $y$ and the group automorphism interchanging $x$ and $y$. \medskip We now give examples of intransitive maps with $D(M)=3$. All except $B(m,n)$ are obtained by the following construction. Let $M$ be a map on $n<6$ vertices having a face of size $n$ incident to all $n$ vertices and suppose that the stabilizer of the face is $D_n$, so that $D(M)=3$. Let $M^r$ be the {\em radial} map obtained by adding a new vertex at the center of the face and joining it to all the original vertices of $M$. Then $Aut(M^r) =D_n$ so $D(M^r)=3$. The underlying graph for $Aut(M^r)$ is $S_1(G)$ where $G$ is the underlying graph of $M$. If $M$ has two such faces, as in map T2, the process can be repeated to get a 2-radial map with underlying graph $S_2(G)$. Examples for intransitive maps are given in Table 2. For the radial types, the column headed by ``map" give the map to which the radial construction is applied. Columns $V$ and $E$ are the number of vertex and edge orbits, respectively. For map N9, we abbreviate the Petrie dual of the tetrahedron by $K_4^P$. We note that by partial Petrie duality, each map in the table can give rise to many other maps. For example, map N10 has $16$ possible partial Petrie duals. We do not give intransitive examples with underlying graph $K(n,n), n=3,4,5$. We will show later that there are such maps only for $n=4$. \begin{center} \begin{tabular}{|l|c|c|c|c|c|l|} \hline ID & Type & map & $G$ & surface & V & E \\ \hline\hline N1-N3 & 1 rad & $C_n, n=3,4,5$ & $S_1C_n$ & sphere & 2 & 2 \\ \hline N4 & 1 rad & T1 & $S_1K_4$ & torus & 2 & 3 \\ \hline N5 & 1 rad & T2 & $S_1K_5$ & $g=2$ & 2 & 3 \\ \hline N6-N8 & 2 rad & $C_n, n=3,4,5$ & $S_2C_n$ & sphere & 3 & 3 \\ \hline N9 & 3 rad & $K_4^P$ & $S_3K_4$ & proj & 2 & 2 \\ \hline N10 & 2 rad & T2 & $S_2K_5$ & $g=2$ & 3 & 4 \\ \hline N11-13 & bipart & $B(m,n), 22$. We must also show that none have $D(M)=4$. \bt If $D(M)=4$, then $M$ is the tetrahedron or its Petrie dual. \et \pr Suppose that $D(M)=4$. Let $uv$ be any edge. If $Stab(u,v)\subset Z_2\times Z_2$ acts on the remaining vertices faithfully, then its distinguishing number in that action is $2$, so $D(M)=3$, a conatradiction. Thus there is $f \in Stab(u,v)$ fixing all other vertices; since it cannot also fix $u$ and $v$, it must interchange them. It is easily proved by induction that a set $E$ of transpositions in the symmetric group $S_n$ generates $S_n$ if and only if the graph on $n$ vertices having $E$ as edges is connected. We have shown for each edge $uv$ in the map $M$, the transposition $(u,v)$, as a permutation of the vertices, is an automorphism. Since the map is connected, $Aut(M)=S_n$, where $n$ is the number of vertices. But $|Aut(M)|\leq 4[n(n-1)/2]=2n(n-1)$, since each edge stabilizer has size at most $4$. Thus $n!\leq2n(n-1)$, so $n\leq 4$. Since $M$ has no vertices of valence $2$, we have $n=4$ and $Aut(M)=S_4$, so $M$ is the tetrahedron or its Petrie dual. \ebox \section{ The Classification Theorem} \bt (Classification Theorem) Suppose that $D(M)=3$ and no vertex of $M$ has valence $1$ or $2$. If $M$ is vertex-transitive, the underlying graph is one of the following: $K_n$ for $n=4,5,6,7,9$; $K_{n,n}$ for $n=3,4,5$; the octahedral graphs $O_6$ and $O_8$; the cube; $K_{3,3,3}$; or $C_3 \times C_3$. If $M$ is not vertex-transitive, then the underlying graph for $M$ is one of the following: $S_kC_n$ for $k=1,2$ and $n=3,4,5$; $S_kK_4$ for $k=1,3$; $S_kK_5$ for $k=1,2$; or $K_{m,n}$ for $32$. \et Moreover, in the following sections, we easily bound the valence $d\leq8$. At that point, with diameter at most $2$ and small valence, maps with $D(M)>2$ are very small, at most $1+8+8\cdot 7=65$ vertices. Indeed, with not much more work one can get the number of vertices to be smaller still. In particular, the Classification Theorem can be proved simply with a computer search. On the other hand, although our overall proof involves some case-by-case analysis, the number of cases is not that large and the proofs are not long. \section{The intransitive case} We note that the orbits under $Aut(M)$ form a kind of coloring, so any question about distinguishability depends on the relative valences of the different orbits. This coloring leads to the banning of certain angles (assume $P,Q,R$ are different orbits):\\ {\em There can be no bent $PQR$ angles.}\\ {\em There can be no bent open $PQQ$ angles} If $P$ and $Q$ are different orbits and $u$ is in $P$, we let $d_{PQ}$ be the number of neighbors of $u$ in $Q$ and $d_{PP}$ the number of neighbors of $u$ in $P$. \bl \label{dPQ} Let $P$ and $Q$ be different orbits. Then\\ a) $d_{PQ} \geq d_{QQ}$ and if $d_{QP}>1$, then $d_{PQ} \geq d_{QQ}+1$;\\ b) if $d_{PQ}>0$, then it divides $d_{PP}$; in particular, if $d_{PP}>0$, then $d_{PQ}\leq d_{PP}$;\\ c) $d_{PQ} <6$;\\ d) if $d_{PP}>0$ and $d_{PQ}>0$, then $d_{QQ}=0$;\\ Note that by symmetry, the same statements hold with $P$ and $Q$ interchanged. \el \pr We let $u$ be a vertex in $P$ and $v$ a vertex in $Q$ adjacent to $u$.\\ {\bf a)} Let $w$ be any vertex in $Q$ adjacent to $v$. Then unless $uvw$ is straight, there must be an edge $uw$ since there are no open bent $PQQ$ angles. Thus $u$ is adjacent to at least $d_{QQ}-1$ of the neighbors of $v$ in $Q$; including the adjacency of $u$ to $v$, we have $d_{PQ} \geq d_{QQ}$. If $d_{QP}>1$, we claim that $u$ must also be adjacent to $w$ even if $uvw$ is straight, so $d_{PQ} \geq d_{QQ}+1$. Suppose not. Since $d_{QP}>1$, then there is another vertex $x$ from $P$ adjacent to $v$. Let $Y=\{u,v,w,x\}$, let $H$ be the subgraph induced by $Y$, and let $f\in Stab(u,v,w,x)$ be nontrivial. Since $v,w \in Q$ and $u,x \in P$, $f$ fixes $v$ since it has valence $3$ in $H$ and $w$ does not. Then $f$ also fixes $w$, but that is impossible since $uvw$ is straight and $xvw$ is not. {\bf b)} For any $PQ$ edge $uv$, there is a reflection $\tau_{uv}$. Thus $Stab(u)$ acts transitively on the $QPQ$ ``corners" at $u$, that is angles $vuv'$ where $v$ and $v'$ are consecutive $Q$ vertices in the rotation at $u$ (there may be intervening vertices from other orbits). Then any $w\in P$ adjacent to $u$ must lie in some $QPQ$ corner and hence has at least $d_{PQ}$ images under $Stab(u)$. Thus $d_{PQ}$ divides $d_{PP}$. {\bf c)} This follows from the original necklace problem. {\bf d)} Suppose instead that $d_{QQ}>0$. From (a) and (b), we have $$d_{PQ} \geq d_{QQ} \geq d_{QP}.$$ Reversing the roles of $P$ and $Q$, we get $d_{QP}\geq d_{PQ}$. Thus $d_{PQ}=d_{QP}=d_{QQ}$. Since $d_{QQ}>1$ implies $d_{PQ}>d_{QQ}$, the common value must be 1. Since there are no vertices of valence 2, we have $d_{QR}>0$ for some third orbit $R$, but then there must be a bent $PQR$ angle or an open bent $PQQ$ angle, a contradiction. \ebox \bl If there are three or more vertex orbits, then the underlying graph $G$ for $M$ is $S_2C_n$, for $n<6$, or $S_2K_5$. \el \pr By connectivity, there must be an angle $uvw$ with the vertices in different orbits $P,Q,R$. Since there can be no bent $PQR$ angles, $u$ and $w$ are the only neighbors of $v$ not in $Q$ and $uvw$ is straight. Since $v$ does not have valence $2$, we have $d_{QQ}>0$, so by part (d) of Lemma \ref{dPQ}, $d_{PP}=d_{RR}=0$. Moreover, $u$ cannot be adjacent to a vertex not in $Q$, since by the same argument as we used for $v$, we would have $d_{PP}>0$. We conclude that both $u$ and $w$ only have neighbors in $Q$. In particular, $P,Q,R$ are the only orbits and $P=\{u\}, R=\{w\}$, since $d_{QP}=d_{QR}=1$. By Lemma \ref{dPQ}, we also have $d_{PQ}<6$ and $d_{PQ}\geq d_{QQ}$, so $|Q|<6$. Since every vertex in $Q$ is like $u$, every vertex in $Q$ has a $P$ and $Q$ neighbor, and since $|P|=|R|=1$, every vertex in $Q$ is adjacent to both $u$ and $w$. Thus $G=S_2H$, where $H$ is the subgraph induced by $Q$. Since the $PQR$ angle $uvw$ is straight, $Stab(uvw)$ includes $\tau_{uv}$, which pairs the $Q$ neighbors of $v$, so $d_{QQ}$ is even. Since $H$ is also vertex-transitive, because of the action of $Stab(u)$ on its $Q$ neighbors, and since $|H|<6$, the only possibilities for $H$ are $C_n$, for $n=3,4,5$ and $K_5$. \ebox The exceptions appear in our list of intransitive maps with $D(M)=3$. \bl Suppose that $d_{PP}=d_{QQ}=0$. Then the underlying graph $G$ for the $M$ is a complete bipartite graph $K_{m,n}$ where $m=3,4,5$ and $n=3,4,5$. \el \pr The graph $G$ is bipartite, with colors $P$ and $Q$. By Lemma \ref{diameter}, the diameter is $2$, so the distance between any vertex in $P$ and any in $Q$, which must be odd, can only be $1$. The limits on $m$ and $n$ follow from (d) of the Lemma \ref{dPQ}. \ebox We observe that our list of intransitive examples includes all the values $2 0$. Then the underlying graph $G$ for $M$ is $S_kC_n$ where $k=1,2$ and $n=3,4,5$; $S_kK_4$ where $k=1,3$; $S_kK_5$ where $k=1,2$. \el \pr Let $u$ be any vertex in $P$. We claim all vertices in $Q$ are adjacent to $u$. If $P=\{u\}$, then $d_{QP}=1$, so all vertices in $Q$ are adjacent to $u$. Suppose instead $u' \in P$. Because the diameter is at most $2$, there must be a $PQP$ path from $u$ to $u'$, since $d_{PP}=0$. Thus $d_{QP}>1$. Suppose that $w\in Q$. Again, there must be a path $uvw$ with $v\in Q$. Since $d_{QP}>1$, by the proof of part (a) of Lemma \ref{dPQ}, $w$ must be adjacent to $u$. Let $21$, the only possibilities for $H$ are $C_n$, for $n=3,4,5$ or $K_4$ or $K_5$. If $d_{QQ}=1$, the only possibility is that $H$ is the disjoint union of $2$ edges. Let $v,w \in Q$ be endpoints of one of those edges. Then the only nontrivial element of $Stab(v)$ is $\tau_{vw}$. Thus if $|P|>1$, some element $z \in P$ is moved by $\tau_{vw}$, so $Stab(v,z)$ is trivial. If $|P|=1$ instead, then $v$ has valence $2$, a contradiction. Thus $d_{QQ}>1$ and $H$ is one of the required graphs. It remains to show $|P|<3$ in all cases, except for $K_4$, where we want $|P|=1,3$. But by Lemma \ref{dPQ}, we have $d_{QQ}$ is divisible by $d_{QP}=|P|$. This restricts $|P|$ to the required values in all cases, except for the possibility $|P|=4$ for $H=K_5$. For this last case, suppose $u,v\in Q$. Then $Stab(u,v)\subset Z_2\times Z_2$ acts on $P$. Since any faithful action of $Z_2\times Z_2$ on a set with $4$ elements has distinguishing number $2$, some nontrivial $f\in Stab(u,v)$ fixes all vertices in $P$. But $f$ also fixes an element of $Q$ since $f$ is an involution and $|Q|=5$, so $f$ fixes a bent $PQP$ angle. \ebox Again, we have provided examples of maps with the given underlying graph $G$. \medskip \section{The vertex-transitive case: regular maps} Our basic plan for the vertex-transitive case is to factor the vertex-transitive map $M$ with $D(M)=3$ into an all-$\tau$ map $M_1$ and a no-$\tau$ map $M_2$; either factor may be disconnected. Since the collection of $\tau$-edges is invariant under the action of $Aut(M)$, the map obtained by restricting the general rotation system only to the edges in $M_1$ or $M_2$ is vertex-transitive and $D(M_1)=D(M_2)=3.$ In \cite{TT}, we found the five graphs underlying no-$\tau$ maps $M$ with $D(M)=3$. Thus, we need to classify the all-$\tau$ maps $M$ with $D(M)=3$, and then see how all-$\tau$ and no-$\tau$ maps can be overlaid with each other. If $M$ is an all-$\tau$ map, then vertex stabilizers are $D_d$ if $d$ is odd and $D_d$ or $D_{d/2}$ if $d$ is even. In the $D_{d}$ case we have a regular (reflexible) map. In the $D_{d/2}$ case, there are two edge orbits and we can again restrict $M$ to one of those orbits to obtain a regular map $M'$. Thus our first task is to classify reflexible regular maps $M$ with $D(M)=3$. Throughout this section, we let $M$ denote a regular (reflexible) map with $D(M)=3$ and underlying graph $G$ of valence $d>2$, and diameter at most $2$. \bt The graph $G$ is $K_n$ for $n=4,6$, $K_{n,n}$ for $n=3,4,5$; $K_{3,3,3}$; $C_3\times C_3$; or $O_6$. \et The proof follows from a number of lemmas. First we handle $K_n$. It is well-known \cite{ST} that the only reflexible regular maps with underlying graph $K_n$ are for $n=3,4,6$. The following proof, however, is astonishingly simple and illustrates the power of angle measure. \bt \label{ref} The only complete graphs $K_n, n>3,$ underlying a reflexible regular map are $K_4$ and $K_6$. \et \pr We note that all triangles are equiangular, since any angle $uvw$ has a reflection fixing $v$ and interchanging $u$ and $w$. We will show that if $M$ has closed angles of measure $1$ and $2$, then the valence $d=5$. Indeed, if angle $uvw$ and $wvx$ have measure $1$ and $uvx$ has measure $2$, then the $K_4$ subgraph induced by $u,v,w,x$ has two triangles with common angle measure $1$ ($uvw$ and $wvx$) and two with common angle measure $2$ ($uvx$ and $uwx$). But then at vertex $u$, the three incident edges make two angles of measure $2$ and one of measure $1$, which can only happen if $d=2\cdot 2+1=5$. If the graph underlying $M$ is $K_n$, all angles are closed, so the only possibilities are $K_6$ for $d=5$ and $K_4$, since it has angles only of measure $1$. \ebox We have not yet given a vertex-transitive map $M$ with $D(M)=3$ and underlying graph $K_6$. There is one, up to Petrie duality: the quotient of the icosahedron under the antipodal map is a regular map triangulating the projective plane by $K_6$. Since vertex-stabilizers are $D_5$, we have $D(M)>2$. Next, for diameter $2$, we bound the valence. \bl\label{dle6} If the diameter of $M$ is $2$, then $d\leq 6$. \el \pr Let $v$ be any vertex and let its neighbors be $u_1,u_2, \dots, u_d$, in cyclic order. Let $Y$ be all the neighbors of $v$ except $u_1, u_2, u_4$ and let $H$ be the subgraph induced by $Y$ and $v$. As long as $d-4\geq d/2$, given any angle measure $a\leq d/2$ and any vertex $u \neq u_3$ in $Y$, there is a vertex $u'$ in $Y$ such that angle $uvu'$ has measure $a$. For $u_3$ the only missing measure is $1$. Thus unless the only open angle measure is $1$, the only vertex in $H$ of valence $d-3$ is $v$. Thus any automorphism stabilizing $H$ fixes $v$, and hence must be trivial, by the necklace problem. If the only open angle measure is $1$, throw out instead the neighbors $u_1,u_4,u_5$. Again, every vertex in $Y$ has valence less than $d-3$, and again the stabilizer of $H$ is trivial, as long as $d>7$; for $d=7$, unfortunately $\tau_{u_1v}$ stabilizes $H$. For $d=7$, we again have trivial stabilizer for $H$, looking at open angles as before, unless the only open angle measure is $1$ or the only open angle measure is $3$. But by the previous lemma, we cannot have both measure $1$ and $2$ closed. Thus the only possibility is for measures $2$ and $3$ to be closed. But then as in the previous lemma, we have a $K_4$ subgraph with two triangles having common measure $2$ and two having common measure $3$. At one vertex of this $K_4$ we have two angles of measure $3$ and one of measure $2$, so $2\cdot 3 +2=8\neq 7$, a contradiction. \ebox Now we handle the remaining valences. \bl For $d=6$, we have $G=K_{3,3,3}$. \el \pr Let $v$ be any vertex and let the vertices of $L=Link(v)$ be, in cyclic order, $u_1, \dots u_6$. Suppose there are two open angle measures. Let $H$ be the graph induced by $v,u_1,u_2,u_4$. If the valence of $v$ is larger than the other vertices, any automorphism stabilizing $H$ fixes $v$, contradicting the necklace problem for $d=6$. By the proof of Lemma \ref{dle6} applied to $d=6$, we cannot have angles of measure $1$ and $2$ both closed, or measures $2$ and $3$. We conclude that the only open angles have measure $2$. Since angles of measures $1$ and $3$ are closed, $u_1$ is adjacent to $u_2, u_6$ and $u_4$, in addition to $v$. Thus $u_1$ is adjacent to two other vertices $w,w'$ that have distance $2$ from $v$. Since all triangles are equiangular, angles $u_1u_2v, u_1u_6v$ have measure $1$ and angle $vu_1u_4$ is straight. Thus the cyclic order at $u_1$ is $v, u_2,w,u_4,w', u_6$. Repeating this argument at vertices $u_2, \cdots u_6$, we conclude that $w$ and $w'$ are adjacent to each of $u_1,\dots, u_6$. Thus $G=K_{3,3,3}$ with parts $\{v,w,w'\}, \{u_1,u_3,u_5\}, \{ u_2,u_4,u_6\}$. \ebox Next we finish the cases $d=3,5$. \bl For $d=3,5$, the possibilities are $G=K_{3,3}$ and $G=K_{5,5}$. \el \pr For $d=3$, since the diameter is $2$, all angles are open, so $G=K_{3,3}$. For $d=5$, if all angles are open then $G=K_{5,5}$. It remains to show for $d=5$ that it is impossible to have one of the angle measures $1,2$ open and one closed (they cannot both be closed since the diameter is $2$). Let $H$ be the subgraph induced by the vertices a distance 2 from $v$ and let $L=Link(v)$. If $u\in L$, then $u$ is adjacent to $v$ and two vertices in $L$, so $u$ is adjacent to two vertices $w,w'$ in $H$, which must be interchanged by $\tau_{uv}$. Thus there are exactly $5\cdot 2=10$ edges between $L$ and $H$. Since one angle measure at $u$ is closed, $w$ is adjacent to two vertices in $Link(u)$. At least one of those two vertices must also be in $L$, since the other neighbors of $u$ are $w,w',v$ and $w$ is not adjacent to $v$. Thus each vertex in $H$ has at least two edges to $L$, so $H$ has at most $5$ vertices. Let $f\in Stab(v)$ have order $5$. If $f(w)=w$, then all edges from $w$ lead to $L$; the same holds for $w'$ since $\tau_{vu}$ interchanges $w$ and $w'$. Thus $H$ consists of two nonadjacent vertices, so $G$ has $8$ vertices. But then the complement is vertex-transitive, with $8$ vertices of valence $2$ and a triangle $vww'$, a contradiction. If instead $f(w)\neq w$ then the orbit of $w$ under $f$ has size $5$ and is all of $H$. In particular, $w$ has exactly two edges to $L$, so $H$ has $5$ vertices, all of valence $3$, which is impossible. \ebox Finally, we handle $d=4$. \bl \label{d=4}If $d=4$, then $G$ is $K_{4,4}, O_6$ or $C_3 \times C_3$. \el \pr If all angles are open, then $G=K_{4,4}$, as in the other cases. Since the diameter is $2$, there must be both open and closed angles. Since there are only two possible angle measures, either bent angles are open and straight are closed, or vice versa. Let $v$ be any vertex, $L=Link(v)$, and $H$ the subgraph induced by vertices a distance $2$ from $v$. If all bent angles are closed and straight angles are open, $G=O_6$, since there are four edges from $L$ to $H$ and vertices a distance 2 apart (for example, at the end of straight angle at $v$) have at least 3 common neighbors, forcing $H$ to be a single vertex. Suppose instead that bent angles are open and straight angles closed. Let $u_1, \dots, u_4$ be the vertices of $L$ in cyclic order around $v$. Then $u_1vu_3$ and $u_2vu_4$ form triangles $T$ and $R$ through $v$ in which every angle is straight; it is best to think of these as perpendicular lines. Since $M$ is regular, there is an automorphism $f$ of order $3$ leaving $T$ invariant; think of $f$ as a translation along the line $T$ taking $v$ to $u_1$ to $u_3$ to $v$. Then $f$ also leaves invariant the straight triangle/line $T'$ through $u_2$ disjoint (or ``parallel") to $T$. Similarly, $f$ takes $R$ to the parallel line $R'$ through $u_1$. This forces a point of intersection $f(u_2)$ of $R'$ and $T'$. Similarly, $f^2(u_2), f(u_4), f^2(u_4)$ give other points of intersection of lines through $u_1, u_2, u_3,u_4$, giving $9$ vertices in all on two perpendicular families of three parallel lines. The result is $C_3\times C_3$. In addition, the automorphism $f$, together with a similar automorphism for the straight triangle $u_2vu_4$, make $M$ a Cayley map for $Z_3\times Z_3$. \ebox \section{The vertex-transitive case: completing the classification} It remains to consider all-$\tau$ nonregular maps and mixed maps. \bt The possible nonregular all-$\tau$ maps $M$ with $D(M)=3$ have underlying graph either $G=K_9$, as an overlay of two copies of a regular map for $C_3\times C_3$, or $G=O_8$, as an overlay of the cube with two tetrahedrons. \et \pr Since $M$ is all-$\tau$ but not regular, there are two edge orbits inducing regular maps $M_1$ and $M_2$, whose edges alternate at each vertex; the maps need not be connected. Let $uvw$ be a corner. Since there is no automorphism taking edge $uv$ to $uw$, the angle must be closed, so there is an edge $uw$. Without loss of generality, we can assume that $uw$ is in $M_1$. Then all edges closing the corners must be in $M_1$ by the transitive action of $Stab(v)$ on the corners at $v$. In particular, if $uv$ is in $M_2$, there is a path of length $2$ in $M_1$ from $u$ to $v$, so $M_1$ is connected and hence contains all vertices of $M$. In addition, $M_1$ contains the cycle $C_{d}$ with alternate vertices joined to $v$ (there may be other edges between vertices in $L$ that are also in $M_1$, but no other edges to $v$). Checking our list of regular maps with $D(M)=3$ for the structure of $M_1$, we find the only possibilities are $C_3 \times C_3$ and the cube. In the first case, the graph $G$ underlying $M$ is $K_9$ so the graph underlying $M_2$ is the complement of $C_3\times C_3$ which is again $C_3\times C_3$. For the cube, $G=O_8$ since the valence is $d=3+3=6$ and there are $8$ vertices. There are various ways to see that the complement in $O_8$ of any cube subgraph is two copies of $K_4$. For example, $O_8$ is $K_8$ with four disjoint edges removed, which we can consider as the four diagonals through the center of the cube; viewing the cube as a bipartite graph, the complement in $O_8$ is then all the edges within the two parts. \ebox \bt The only mixed map $M$ with $D(M)=3$ is $CM(Z_4, (1,-1,2))$ and its three partial or full Petrie duals. \et \pr Let $M_1$ be the all-$\tau$ map induced by $\tau$ edges and $M_2$ be the no-$\tau$ map induced by the remaining edges; both maps could be disconnected. Denote their valences by $d_1$ and $d_2$, respectively. Whether $M_1$ is regular or not, $Aut(M)$ acts transitively on the corners of $M_1$, so $d_1$ divides $d_2$. Also, if $uv$ is in $M_1$, then $\tau_{uv}$ fixes no neighbor of $u$ in $M_2$, so $d_2$ is even. We claim that $M_2$ is connected. It suffices to show that for any edge $uv$ in $M_1$, there are edges $uw$ and $wv$ in $M_2$. Suppose not. If $w$ is any neighbor of $u$ in $M_2$, then the angle $vuw$ must be bent since $uv$ is a $\tau$ edge but $uw$ is not. Since there is no automorphism fixing $u$ and interchanging edges $uv$ and $uw$, the angle $vuw$ must be closed, so there is an edge $vw$. By our assumption, $vw$ is in $M_1$. But then for each of $d_2$ neighbors $w$ of $u$ in $M_2$, there is an edge $vw$ in $M_1$, which implies $d_1>d_2$, a contradiction. Thus $M_2$ is connected and its underlying graph spans $M$. Suppose that $d_2>2$. Then $Aut(M)$ acts faithfully on $M_2$, so $D(M_2)=3$. In this case, since $d_2$ is even, we must have by Theorem \ref{D+} that the graph underlying $M_2$ is $K_5,K_7, O_6$ or $O_8$. It cannot be $K_5$ or $K_7$, since that would make $M_1$ empty. If it is either $O_6$ or $O_8$, then there is only one edge from $M_1$ incident to any vertex $v$. But then the vertex stabilizer in $Aut(M)$ has order at most two, which is not the case for any group acting with distinguishing number $3$ on a map with underlying graph $O_6$ or $O_8$. We conclude that $d_2=2$ so the graph underlying $M_2$, is $C_n$ for $n=3,4,5$. Since $M_1$ is not empty, $n\neq 3$. For $n=5$, the graph underlying $M_2$ is also $C_5$ and for any edge $uv$ in $M_1$, we have $\tau_{uv}$ fixing exactly two of five vertices in $C_5$, which is impossible. For $n=4$, the underlying graph is $K_4$, so we can simply enumerate all transitive subgroups of the symmetric group $S_4$ with blocks $13$ and $24$ and containing the involutions $(13)$ and $(24)$ (all permutations in $S_4$ can be realized by automorphisms of the standard tetrahedron map). The only such subgroup is generated by $(1234)$ and $(13)$ and is therefore the same as $Aut(CM(Z_4,(1,-1,2)))$. \ebox \section{ Comments} We have not classified maps $M$ with $D(M)>2$; rather we have classified the underlying graphs. A careful count, eliminating duplications such as $S_1(K_4)=K_5$, gives $22$ different graphs having no vertex of valence $1$ or $2$. If instead we want to count maps, then things get very complicated. For example, the graph $S_2(K_5)$ underlying $N10$ (the double radial map of $T2$) has $4$ edge orbits $E_1, \dots, E_4$ under a $D_5$ action, which would appear to lead to $2^4=16$ different maps using all partial and full Petrie duals. On the other hand, there is also an automorphism $f$ of T2 interchanging the edge orbits in pairs $E_1$ with $E_2$ and $E_3$ with $E_4$, so, for example, the Petrie dual twisting only edges in $E_1$ is isomorphic to the one twisting edges only in $E_2$. In this way, $f$ is an automorphism of 4 of the 16 maps and pairs the remaining 12, so there are only 10 isomorphism classes of maps, not 16. As another example, the graph $K_5$ underlies three very different maps with $D(M)=3$: a chiral regular embedding in the torus (which gives two maps because of the orientation), the transitive but non-regular map $T2$, and the intransitive map $N_4$; moreover, each of these maps have various partial Petrie duals. In the transitive case, many of our arguments classify the map up to Petrie duality (see for example, Lemma \ref{d=4} in the case $C_3\times C_3$). In \cite{TT}, we also classify the maps $M$ with $D^+(M)=3$. We suspect that with more effort, we could also classify the maps in the intransitive case. Finally, our results should be compared with Theorem 6 of Negami \cite{N}, which gives a partial classification of graphs underlying polyhedral maps $M$ with $D(M)=3$. A map is {\em polyhedral} if every face boundary is a cycle and the intersection of two face boundaries is either empty, a single vertex, or a single edge. This is a major restriction eliminating all the maps of Theorem 3.1 and 3.2 except those for $K_{2,n},K_4, K_7, O_6$, and all the vertex-transitive maps from Table 1 except T3,T6, T7. It also eliminates the intransitive maps N4, N5, N10, N11-N13. In addition, Negami leaves open the possibility that there are maps with $D>2$ for some or all of the complete graphs $K_8,K_n, n\geq 10$ and for the complement of $K_6\times K_2$. As we have shown, there are none. Negami's methods are completely different from the methods in this paper. \begin{thebibliography}{xx} \bibitem{AC1} M. Albertson and K. Collins, Symmetry breaking in graphs, {\em Electron. J. Combin. } {\bf 3} (1996), R18. \bibitem{GT} J. L. Gross and T. W. Tucker, {\em Topological Graph Theory}, Wiley 1987 and Dover 2000. \bibitem{N} S. Negami, The distinguishing numbers of graphs on closed surfaces, {\em Discrete Math.} {\bf 312} (2012), 973-991. \bibitem {RSJTW} R. B. Richter, J. \v Sir\' a\v n, R. Jajcay, T. W. Tucker and M. E. Watkins, Cayley maps, {\em J. Combin. Theory Ser. B}, {\bf 95} (2005), 189-245. \bibitem{ST} J. \v Sir\' a\v n, T. W. Tucker, Symmetric Maps, in {\em Topics in Topological Graph Theory}, eds Beineke and Wilson, Cambridge University Press, 2009. \bibitem{TT} T. W. Tucker, Distinguishing maps, {\em Electron. J. Combin.}, {\bf 18} (2011), P50. \end{thebibliography} \end{document}