Special case of [this question](https://mathoverflow.net/questions/152442/graphs-with-many-edges-avoided-by-hamiltonian-cycles).


Let $G$ be $r$-regular Hamiltonian graph.


An $a$ edge is an edge which is on every Hamiltonian cycle.
A $b$ edge is an edge which is on no Hamiltonian cycle.
$a(G)$ and $b(G)$ are numbers of $a$ and $b$ edges.


Assume $a(G)>0$.


Define $ \rho(G)=\dfrac{b(G)}{a(G)}$.



> 
> What are upper bounds for $\rho(G)$?
> 
> 
> 




---


Partial results.


The linked question showed for cubic graphs $\rho(G) \le \frac12$.


For $4$-regular graphs search by `nvcleemp`
showed the largest $\rho(G)$ on up to $14$ vertices is $1$
other being $\frac12,\frac13$.



> 
> What about $4$-regular graphs? Is $1$ upper bound?
> 
> 
> 


This might show uniquely Hamiltonian $r$-regular graphs don't exist.


An example of $4$-regular with $\rho(G)=1$ (maybe the smallest) is:



```
 [(0, 4), (0, 6), (0, 8), (0, 9), (1, 5), (1, 7), (1, 10), (1, 11), (2, 6), (2, 8), (2, 9), (2, 10), (3, 7), (3, 9), (3, 10), (3, 11), (4, 6), (4, 8), (4, 9), (5, 7), (5, 10), (5, 11), (6, 8), (7, 11)]

```


Regular graphs with $a$ and $b$ Hamiltonian edges
There are infinite families of $4$ and $5$ regular graphs
with $\rho(G)=1$ using a gadget.


A gadget is graph $GA$ with $2$ vertices $u,v$ of degree $d-1$
and the rest are of degree $d$. The gadget contains
sufficiently many $b'$ edges which are no $uv$ Hamiltonian path
compared to $a'$ edges which are on all H-$uv$ paths.


Take $n$ copies of $GA$ connect the $u,v$ edges in cycles.


An example a $GA\_5$ whith one $b'$ edge and no $a'$ edges is:



```
GA_5=[(0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (2, 3), (2, 4), (2, 5), (2, 6), (3, 6), (3, 7), (4, 6), (4, 7), (5, 7)]
b'=(2,5)

```

The $5$-regular graph of two $GA\_5$.



```
[(0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (2, 3), (2, 4), (2, 5), (2, 6), (2, 13), (3, 6), (3, 7), (4, 6), (4, 7), (5, 7), (5, 10), (8, 11), (8, 12), (8, 13), (8, 14), (8, 15), (9, 11), (9, 12), (9, 13), (9, 14), (9, 15), (10, 11), (10, 12), (10, 13), (10, 14), (11, 14), (11, 15), (12, 14), (12, 15), (13, 15)]

```



---


For $4$-regular $\rho(G)=2$ is possible using a similar gadget.


graph6 string:



```
 W?`DDD[VBgPW????A?@????_?@??D??DC?@[??V??Bg??PW

```

