Greedy Algorithm Proof Min Swaps Problem to get the min. no. of swaps required for arranging pairs togethe.

There exists an array of size 2N with integers ranging from 0 to 2N-1 arranged at random. Each integer is paired with another
i.e. 0 paired with 1, 2 paired with 3,...2N-2 paired with 2N-1. What is the minimum number of swaps required to have 
all pairs next to each other.
E.g. : [5,4,2,6,3,1,0,7] -&gt; [5,4,2,3,0,1,6,7] Output 2 swaps needed

Solution: Greedy Approach

for i from 0 to 2N-2:
    if array[i] and array[i+1] does not constitute a pair:
        find the pair for the ith one and swap position with i+1 element


What is the proof for why the above greedy algorithm is optimal?
The algorithm in the question can be stated more clearly in the following form since considering the odd $i$ does not have any effect once $i-1$ has been take care of.

for even i from 0 to 2N-2:  
    if array[i] and array[i+1] does not constitute a pair:
        find the pair for the i-th one and swap position with i+1 element




Here is an outline of the proof.

Given an array $A$ of size $2N$ with integers ranging from $0$ to $2N-1$, let us construct a graph $G$. Replacing $2i-1$ with $2(i-1)$ for all $i$, we will have a new array $B$ of even integers from $0$ to $2(N-1)$, each of which appears twice. Let $G$ have vertices $0, 2, \cdots, 2(N-2)$. 


If $B[0]=2i$ and $B[1]=2j$, we will add an edge between $2i$ and $2j$ in $G$.
If $B[2]=2i$ and $B[3]=2j$, we will add an edge between $2i$ and $2j$ in $G$.
$\cdots$
If $B[2N-2]=2i$ and $B[2N-1]=2j$, we will add an edge between $2i$ and $2j$ in $G$.


Please note since $2i$ might be the same as $2j$, $G$ may have self-loops. Since each even number appears twice in array $B$, the degree of each of vertices of $G$ is 2 (2-regular graph). That means $G$ is a disjoint union of cycles. 

Define a function $s$ from arrays which are permutations of $0, 1, \cdots, 2N-1$ to $\Bbb N$, $s(A)=$ the number of cycles in $G$, where $G$ is obtained from $A$ by the above deterministic construction.

Claim (at most 1 increase with one swap). Suppose an array $A$ is changed to $A'$ by a swap of two elements. Then $s(A')\le s(A)+1$.

Suppose we have proved the claim. Notice that $s(A)=N$, the maximum value of $s$ if and only if all pairs are next to each other. Since you can only increase at most 1 to $s(A)$ by each swap and the greedy algorithm does increase $s(A)$ by 1 with each of its swaps, the greedy algorithm must be optimal.



I will leave the gaps in the above proof as two easy exercises.

Exercise 1: The greedy algorithm increase the value of $s$ by 1 with each of its swaps.

Exercise 2: Prove the claim of at most 1 increase with one swap.