Discrete Equations

Question 1

Sum of vertices =

Answer 1

2 x number of edges

each edge has two ends

Question 2

Number of edges on complete graph with n vertices Kn =

Answer 2

n(n-1)/2
each vertex will connect to all the others hence (n-1)
there are n vertices hence n
divide by 2 because you’ll get a repeat from the forwards/backwards

Question 3

Number of Hamiltonian cycles for complete graph Kn=

Answer 3

(n-1)!/2
choose start vertex then for 2nd vertex there are n-1 options, for 3rd vertex there are n-2 options and so on hence the factorial
divide by 2 because each cycle will be repeated forwards backwards