Given an undirected graph G = (V, E), determine whether G is a complete graph

Question

I'm pretty sure this problem is P and not NP, but I'm having difficulty coming up with a polynomially bound algorithm to solve it.

Answer 1

You can :

1. check that number of edges in the graph is n(n-1)/2.
2. check that each vertice is connected to exaclty n-1 distinct vertices.

This will run in O(V²), which is polynomial.

Hope it helped.