Algorithm to find the number of edges in a graph with vertices defined by a set

Question

I have a graph that is defined as such:

There is a set of numbers {1,2,3,4,5}

Each vertex in the graph can be made of a combination of any 3 numbers in the original set, without repetition. So, for example, a valid vertex would be {1,2,3}.

An edge exists between any two vertices that differ in exactly 1 number. So, there would be an edge between {1,2,3} and {1,2,4}, but no edge between {1,2,3} and {2,4,5}.

How can I write an algorithm to find the number of edges in this graph? I'm having counting some edges twice in my algorithm. I'm not sure what the right method of approaching this is. I know there are 5 choose 3 number of vertices.

Answer 1

C(5,3) in just 10, so it is not very hard to calculate edges.

Simpler way: get any combination and find number of edges:

combination
1  2  3 
subcombinations:
1  2         paired 1 2 4; 1 2 5
1     3      paired 1 3 4; 1 3 5
   2  3      paired 2 3 4; 2 3 5

So we have six edges from this combination vertex. But from the symmetry, every vertex has 6 edges. Such graph is called 6-regular.

So overall number of edges is (divide by 2 to eliminate double counting for every edge)

10 * 6 / 2 = 30 

If you really need general solution for C(n,k) combinations:

p = C(n,k) = n!/(k!*(n-k!)) 
NumEdges = p*k*(n-k)/2