My graph theory book postulates the if a simple graph with n vertices has at least C(n - 1, 2) + 2 edges then the graph must be Hamiltonian. This is probably true but I am confused by the notation of what C(n - 1, 2) means? C usually represents a cycle but clearly not in this case. And whatever function they are referencing takes 2 parameters which is quite strange.

onetreehillyg

onetreehillyg

Open question

2022-08-19

My graph theory book postulates the if a simple graph with n vertices has at least C(n - 1, 2) + 2 edges then the graph must be Hamiltonian.
This is probably true but I am confused by the notation of what C(n - 1, 2) means?
C usually represents a cycle but clearly not in this case. And whatever function they are referencing takes 2 parameters which is quite strange.

Answer & Explanation

Ben Reese

Ben Reese

Beginner2022-08-20Added 12 answers

It is the binomial coefficient n 1 choose 2, i.e.
( n 1 2 ) ,
which is
( n 1 ) ( n 2 ) 2 .
In general, C ( n , k ) is alternative notation used for the binomial coefficient ( n k ) , which is defined by
( n k ) = n ! k ! ( n k ) ! .

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Elementary geometry

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?