Fearful asymmetry

Question

An asymmetric graph (or identity graph) has every vertex unique: no different relabeling of the vertices leaves the edges unchanged.

The trivial graph on one vertex is (trivially) asymmetric. All graphs from 2-5 vertices have at least one symmetry. For six vertices, there are eight asymmetric graphs...but there is only one of them with exactly six edges. (the one shown in the upper left). Similarly, only one has exactly 9 edges.

Though comparatively rare among very small graphs, asymmetric graphs become overwhelmingly common with increasing order...indeed 'almost all' graphs are asymmetric.

so to recap, for

(v=1,e=0) (v=6,e=6) (v=6,e=9)

there exists a unique asymmetric graph with exactly v vertices and e edges.

For what other values of v and e (if any), is this the case?

Answer 1

Short answer:

$\bullet$ $(9,7)$,
$\bullet$ $(1+\sum_{k=7}^nka_k,\sum_{k=7}^n(k-1)a_k)$ for $n\ge7$, where $a_k$ is the number of asymmetric trees on $k$ vertices, and
$\bullet$ their complements $(v,\binom v2-e)$.

Pictures:

$(9,7)$:

The first three in the sequence:

$(8,6)$:

$(16,13)$:

$(43,37)$:

Long answer:

${\large\textbf{Finding asymmetric trees}}$

Facts: A tree has at least as many leaves as its maximum degree. A tree with $2$ degree-$3$ vertices has at least $4$ leaves.

Let $T$ be an asymmetric tree with $n\ge7$ vertices and $\ell\ge2$ leaves. Then no pair of leaves shares a neighbor, otherwise we could switch that pair. In particular, $\ell\le\frac n2$. Also, $\ell>2$, otherwise $T$ would be a path, which is not asymmetric.

Suppose $n=7$. Then $\ell=3$. Then $T$ cannot have any vertices of degree greater than $3$ nor more than one degree-$3$ vertex, so to avoid being a path it must have exactly one degree-$3$ vertex $v$. Then deleting $v$ from $T$ produces $3$ disjoint paths on $6$ vertices. The lengths of these paths sum to $3$ and must be distinct to maintain asymmetry, so they must be $0$, $1$, and $2$. Therefore, there is a unique asymmetric tree on $7$ vertices.

Suppose $n=8$. Then $\ell=3$ or $\ell=4$.

Suppose $\ell=4$. Then $T$ has a degree-$4$ vertex or $2$ degree-$3$ vertices. If $T$ has a degree-$4$ vertex, then it cannot contain any other vertices of degree greater than $2$, so similar to the $n=7$ case, we must partition $3$ into $4$ distinct parts, but this is impossible. If $T$ has $2$ degree-$3$ vertices, then the only way to avoid one of them having $2$ adjacent leaves is to make them adjacent with one neighbor added to one neighbor of each. But then $T$ is symmetric across the edge between the degree-$3$ pair. Therefore, $\ell\neq4$.

Then $\ell=3$. Similar to the $n=7$ case, we must partition $4$ into $3$ distinct parts, which is uniquely done by $0+1+3$. Therefore, there is a unique asymmetric tree on $8$ vertices.

Suppose $n\ge9$. Then we can produce multiple asymmetric trees with a unique vertex of degree at least $3$, having degree exactly $3$, by partitioning $n-4$ into distinct parts as $0+1+(n-5)$ and $0+2+(n-6)$ because $2<n-6$. Therefore, there are multiple asymmetric trees on $n$ vertices for any $n\ge9$.

${\large\textbf{Narrowing down the candidates}}$

Lemma 1: Let $G$ be a connected asymmetric graph whose complement is connected with $n>1$ vertices and $m$ edges. Then there exists a connected asymmetric graph whose complement is connected with $n+1$ vertices and $m+1$ edges.

Proof: Let $v_1,\dots,v_k$ be a longest path in $G$. Let $G_1$ (resp. $G_2$) be $G$ with an added vertex $v_0$ (resp. $v_{k+1}$) adjacent to $v_1$ (resp. $v_k$). Suppose $G_1$ and $G_2$ have nontrivial symmetries $\phi_1$ and $\phi_2$. Because $v_0,\dots,v_k$ is the unique longest path in $G_1$, $\phi_1$ must map this path to itself in reverse, i.e., $\phi_1(v_i)=v_{k-i}$ for all $0\le i\le k$. Similarly, $\phi_2$ must map the path $v_1,\dots,v_{k+1}$ in $G_2$ to itself in reverse. Then $G$ has no vertices outside this path: Suppose not. Let $i=\min\{j:1\le j\le k,d_G(v_j)\ge3\}$ (by maximality, the added vertex cannot be adjacent to an end, so $i>1$). Then $\phi_2(v_i)=v_{k+2-i}$, so $d_{G_2}(v_{k+2-i})\ge3$. Also, $\phi_1(v_{k+2-i})=v_{i-2}$. If $v_{k+2-i}=v_k$, then $d_G(v_{k+2-i})\ge2\implies d_{G_1}(v_{i-2})\ge2$ but $v_{i-2}=v_0$, a contradiction. Otherwise, $d_G(v_{k+2-i})\ge3\implies d_G(v_{i-2})=d_{G_1}(v_{i-2})=d_{G_1}(v_{k+2-i})\ge3$, so $i-2$ contradicts the minimality of $i$. Therefore, $G$ is a path on more than $1$ vertex, contradicting its asymmetry. Thus, $G_1$ or $G_2$ must be asymmetric. Because the complement of $G$ is connected and the added vertex has only one neighbor, the complements of $G_1$ and $G_2$ are also connected. $\square$

Lemma 2: There exists a connected asymmetric graph whose complement is connected on $n\ge6$ vertices and $m$ edges for all $n-1\le m\le\binom n2-(n-1)$, except for $n=6$ and $m=5$ or $m=10$.

Proof: Induct on $n$. We know $n=6$. Because the property of being a connected asymmetric graph whose complement is connected is closed under complements, it suffices to show the claim for $n-1\le m\le\frac12\binom n2$. We know $n=7$ and $m=6$. For $n=7$ and $m\neq6$ or $n>7$, applying Lemma 1 to the connected asymmetric graphs on $n-1$ vertices with $n-2$ to $\binom{n-1}2-(n-2)$ edges, whose complements are connected, produces connected asymmetric graphs on $n$ vertices with $n-1$ to $\binom{n-1}2-(n-2)+1\ge\frac12\binom n2$ edges, which gives the desired result. $\square$

Lemma 3: If there exists an asymmetric graph on $n$ vertices with $m_0<n-1$ edges, then there exist multiple asymmetric graphs on $n$ vertices with $m$ edges for all $m_0<m\le n-2$.

Proof: Induct on $m$. Let $G$ be an asymmetric graph on $n$ vertices with $m_0\le m<n-2$ edges. Then $G$ has at least $3$ components. Pick a pair of components with the fewest vertices, say $G_1$ with $n_1$ vertices and $G_2$ with $n_2$ vertices. Let $G_i$ be the largest component of $G$ excluding $G_1$, say with $n_i$ vertices. Put $G_j=G_2$ and $n_j=n_2$. Because $G$ is asymmetric, each component is asymmetric and distinct, so $n_i\ge6$ or $n_j\ge6$. Then $G_i$ and $G_j$ together have at least $7$ vertices and between $n_i+n_j-2$ (trees) and $\binom{n_i}2+\binom{n_j}2-2$ (complete graphs missing an edge) edges. Because $\binom{n-i}2+\binom{n_j}2-1\le\binom{n_i+n_j}2-(n_i+n_j-1)$, we cause use Lemma 2 to replace $G_i$ and $G_j$ with a connected asymmetric graph with $n_i+n_j$ vertices and one additional edge. The new component is guaranteed to be distinct from the others because we chose a largest component to combine, excluding $G_1$ which is one of the smallest, so the new graph is asymmetric with one added edge. We can perform this same procedure to combine a largest pair of components excluding $G_2$ to produce another asymmetric graph with one added edge. These two graphs are distinct because only one has $G_1$. This completes the induction. $\square$

Lemma 4: There exist multiple asymmetric graphs on $n\ge7$ vertices and $m$ edges for all $n-1\le m\le\frac12\binom n2$, except for $n=7$ and $m=6$.

Proof: Fix $n$ and $m$. By Lemma 2, there exists a connected asymmetric graph on $n$ vertices and $m$ edges. To produce a distinct asymmetric graph, we can use Lemma 2 to find a connected asymmetric graph on $n-1$ vertices and $m$ edges (because $m\le\frac12\binom n2\le\binom{n-1}2-(n-1-1)$) and add a singleton, producing a disconnected asymmetric graph. $\square$

Because asymmetry is preserved under complements, it suffices to find unique asymmetric graphs on $n$ vertices and $m$ edges where $m\le\frac12\binom n2$. Then combining Lemma 3 and Lemma 4, it suffices to determine for each $n$ whether there is a unique asymmetric graph on $n$ vertices with the minimum number of edges among all asymmetric graphs on $n$ vertices.

${\large\textbf{Finding the graphs}}$

Let $G$ be such a graph. The components of $G$ must be connected, asymmetric, edge-minimal, and distinct. We have shown that the only such graphs are the asymmetric trees and $(6,6)$-graph.

Observation 1: If $G$ has the asymmetric $(6,6)$-graph as a component, then it has no other components; otherwise, if the largest other component of $G$ were a $k$-vertex asymmetric tree, then we could replace these two components with a $(k+6)$-vertex asymmetric tree, maintaining the asymmetry and number of vertices and edges of $G$, contradicting uniqueness.

Observation 2: If $G$ has the $7$-vertex asymmetric tree as a component, then it must have the singleton; otherwise, by Observation 1 it does not include the $(6,6)$-graph as a component, so we could replace the $7$-vertex asymmetric tree with the singleton and the $(6,6)$-graph.

Observation 3: If $G$ has a $k$-vertex asymmetric tree as a component, then it must have every $k$-vertex asymmetric tree as a component, otherwise $G$ would not be unique.

Observation 4: If there exists a $k$-vertex asymmetric tree that $G$ does not have as a component, then $G$ cannot have two components with more than $k$ vertices; otherwise, if $G$ has $p$- and $q$-vertex asymmetric trees ($G$ cannot have the $(6,6)$-graph by Observation 1) where $p,q>k$, then they could be replaced by $k$- and $(p+q-k)$-vertex asymmetric trees.

Because there are multiple $k$-vertex asymmetric trees for $k\ge9$, Observations 3 and 4 imply that if $G$ has a component with more than $8$ vertices, then the components of $G$ cannot skip any asymmetric trees, i.e., for some $n$, the components of $G$ are exactly the asymmetric trees of at most $n$ vertices. Call this graph $G_n$. Observe that $G_n$ is indeed uniquely edge-minimal for any $n>0$ because any other asymmetric graph with the same number of vertices as $G_n$ would need to have fewer components or the same number but include the $(6,6)$-graph.

By Lemma 4 and Observations 1 and 2, if $G$ has no component with more than $8$ vertices and is not a $G_n$, the only remaining candidate for $G$ besides the $(6,6)$-graph is the disjoint union of the singleton and the $8$-vertex asymmetric tree, which is easily seen to be edge-minimal.

We have now found the unique edge-minimal asymmetric graphs besides the two given in the question: $G_n$ and the disjoint union of the singleton and the $8$-vertex asymmetric tree. The desired asymmetric graphs unique for their vertex and edge counts are then these and their complements. From here it is easy to count vertices and edges in terms of the number of asymmetric trees with $n$ vertices, which can be found elsewhere. If you've made it this far, congratulations! We are done. $\square$

I look forward to seeing a more clever solution.

Answer 2

Not a full solution by any means, but I'm fairly sure $V=8, E=7$ has a unique asymmetric graph:

 *-*-*-*-*-*-*
         |
         *

(not sure how to spoiler code)

We can also throw in an extra unconnected vertex to get $V=9, E=7$.

We have no asymmetric trees for $V \le 6$. We get multiple asymmetric trees for $V \ge 9$. For $V = 7$, there's one, but it has the same number of edges and vertices as the $V=6, E=6$ graph with an unconnected vertex. Thus, there are no other trees which will work.

Answer 3

I have little graph theory background, so I'll try a computational approach.

If we consider a $v \times v$ adjacency matrix with $2e$ ones, relabeling vertices involves swapping pairs of columns and rows. For example relabeling vertex 1 and 2 is equivalent to swapping the first and second rows and columns, or multiplying by the appropriate permutation matrices.

Here is the adjacency matrix of the first graph: $$ A = \begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ \end{bmatrix} $$

The brute force approach is to generate all possible adjacency graphs and trying all permutations and checking for automorphisms:

$$P^{-1}AP \ne A \quad \forall P$$

Someone with more math background can tell me if this equation actually holds.