两个被出烂了的图论构造

1、对于一个奇数（$=n$）个点的完全图，其边集能被分为$\frac{n-1}{2}$个哈密顿圈的并。

将点按照$1,...,n$编号，设$f(x,y):=\begin{cases}x+y,x+y\leq n-1;\\x+y-n+1,x+y\geq n;\end{cases}$并设$g(x):=\begin{cases}n-x,2x\leq n-1;\\n+1-x,2x\geq n+1;\end{cases}$，那么，第$i$个哈密顿圈由如下边组成：

$$\left<n\mid f(1,i-1)\right>,\left\{\left<f(g^{j-1}(1),i-1)\mid f(g^j(1),i-1)\right>\right\}_{j=1}^{n-2},\left<f(g^{n-2}(1),i-1)\mid n\right>.$$

2、对于一个偶数（$=n$）个点的完全图，其边集能被分为$n-1$个完全匹配的并。

将点按照$1,...,n$编号，设$f(x,y):=\begin{cases}x+y,x+y\leq n-1;\\x+y-n+1,x+y\geq n;\end{cases}$，那么，第$i$个完美匹配由如下边组成：

$$\left<n\mid f(\frac n2,i-1)\right>,\left\{\left<f(j,i-1)|f(n-j,i-1)\right>\right\}_{j=1}^{\frac n2-1}.$$