Kourovka Notebook Problem 20.71

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple undirected graph of order $n=|V|\geq 1$. For $v\in V$, the card associated with $v$ is the induced subgraph \[ G-v:=G[V\setminus\{v\}]. \] Write $[H]_{\cong}$ for the isomorphism class of a graph $H$, and define \[ c(G):=\left|\{[G-v]_{\cong}:v\in V\}\right|. \] Let $\operatorname{Aut}(G)$ be the group of bijections $\alpha:V\to V$ satisfying \[ \{u,v\}\in E\iff\{\alpha(u),\alpha(v)\}\in E \qquad(u,v\in V, \ u\ne v). \] Its orbit through $v$ is $\operatorname{Aut}(G)\cdot v=\{\alpha(v):\alpha\in\operatorname{Aut}(G)\}$. Define the number of vertex orbits by \[ o(G):=\left|\{\operatorname{Aut}(G)\cdot v:v\in V\}\right|. \] For each of the following values of $k$, determine whether \[ \exists\,G\text{ finite, simple, undirected and connected} \quad\text{such that}\quad c(G)=k\quad\text{and}\quad o(G)>k: \] \[ \text{(a) }k=2,\qquad \text{(b) }k=3,\qquad \text{(c) }k=4. \] The supplied source observes that $o(G)\geq c(G)$, and reports that $c(G)=1$ implies that $\operatorname{Aut}(G)$ acts transitively on $V$. It also reports examples with $(c(G),o(G))=(5,6)$ and $(6,7)$; the passage describing these examples does not explicitly state whether they are connected.

The supplied registry labels the overall problem partially solved. Its dated curation reports an affirmative answer to part (c), attributed to J. Prajapati's 2026 preprint. This is a supplied literature assessment, not an independently verified result here. Parts (a) and (b) remain questions in the supplied record. The record lists V. Pannone as proposer and prefixes the statement with "(J. Lauri)"; the relationship between these attributions is unspecified.

Short English statement

For each $k\in\{2,3,4\}$, does there exist a finite connected simple undirected graph with exactly $k$ isomorphism types of vertex-deleted cards but more than $k$ vertex orbits under its automorphism group? The supplied dated curation reports an affirmative answer for $k=4$; it supplies no resolution for $k=2$ or $k=3$.

Sources

• Local UnsolvedMath registry, supplied complete record with permanent ID $701729$, exact source problem code catalogue entry, title Kourovka Notebook Problem 20.71. The registry lists V. Pannone as proposer, with proposed year 2022; the statement separately names J. Lauri.
• The Kourovka Notebook (Unsolved Problems in Group Theory), 20th issue (2022), problem 20.71; also the supplied 21st issue edition (2026), identified as arXiv:1401.0300v48. The registry describes the collection as Issues 1--21 (1965--2026), edited by E. I. Khukhro and V. D. Mazurov.
• J. Prajapati, Preprint, 2026, cited by the supplied Notebook discussion for an affirmative answer to part (c): https://kourovkanotebookorg.wordpress.com/wp-content/uploads/2026/10/kourovka-20-71-prajapati.pdf. No preprint title is supplied.
• The supplied status review is dated 2026-10-16, labels the overall problem partially solved, and identifies the maintained source as its evidence. It reports that part (c) is marked solved in the October 2026 21st issue, arXiv:1401.0300v48. This assessment is supplied dated curation and has not been independently verified here.