You can implement the requirements you lay out pretty quickly using php's array_* functions (which I'll do below), but I would be remiss to not call out that the presented solution limits you to an array of just 4 vertices specifically because of this statement:
if i select the vertices 0 and 1, I am then left with the weight between vertex 2 and 3 because vertex 0 and 1 has already been used.
If you have to interact with 5 vertices, the "remaining weight" aspect increases in complexity since you have more than just a left over unused pair. You'll have to define the desired behavior in the case of 5+ vertices to get more assistance if you are not able to modify the code provided below which solves your case of 4.
<?php
$array = array(
0=> array(0, 2, 20,4),
1=> array(2,0,7,8),
2=> array(20,2,0,12),
3=> array(4,8,12,0)
);
// Use the keys as the list of vertices.
$vertices = array_keys($array);
// Filter out nodes without weights (preserves array keys, which are used as index-relations to other nodes)
$array = array_map('array_filter', $array);
// Create a list of all valid pairs
$fullPairs = array_reduce(array_map(function($vert1, $otherVerts) use ($vertices) {
// For each first vertice, create pair combinations using weighted edge and remaining vertices
return array_map(function($vert2) use ($vert1, $vertices) {
// Because reverse combinations are not desired, we sort the pairings to easily identify dupes
$vert = array($vert1, $vert2);
sort($vert);
$vertPair = array($vert, array_values(array_diff($vertices, $vert)));
usort($vertPair, function($v1, $v2) { return reset($v1) - reset($v2); });
return $vertPair;
}, array_keys($otherVerts));
}, $vertices, $array), 'array_merge', array());
// Unique the list using a string representation of the pairs
$uniqueIndexes = array_unique(array_map('json_encode', $fullPairs));
// Match up the indexes of the unique list against the full pair list to get the pairing structure
$uniquePairs = array_intersect_key($fullPairs, $uniqueIndexes);
// Print the pairings for verification
print_r(array_map('json_encode', $uniquePairs));
// Array
// (
// [0] => [[0,1],[2,3]]
// [1] => [[0,2],[1,3]]
// [2] => [[0,3],[1,2]]
// )