## Saturday, November 12, 2016

### 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/