Check whether given degrees of vertices represent a Graph or Tree

http://www.geeksforgeeks.org/check-whether-given-degrees-vertices-represent-graph-tree/

The degree of a vertex is given by the number of edges incident or leaving from it.
This can simply be done using the properties of trees like –

1. Tree is connected and has no cycles while graphs can have cycles.
2. Tree has exactly n-1 edges while there is no such constraint for graph.
3. It is given that the input graph is connected. We need at least n-1 edges to connect n nodes.

If we take the sum of all the degrees, each edge will be counted twice. Hence, for a tree with n vertices and n – 1 edges, sum of all degrees should be 2 * (n – 1). Please refer Handshaking Lemma for details.

bool check(int degree[], int n)

{

    // Find sum of all degrees

    int deg_sum = 0;

    for (int i = 0; i < n; i++)

        deg_sum += degree[i];

 

    // Graph is tree if sum is equal to 2(n-1)

    return (2*(n-1) == deg_sum);

}

http://www.geeksforgeeks.org/check-whether-given-degrees-vertices-represent-graph-tree/