# Check whether given degrees of vertices represent a Graph or Tree

Given the number of vertices and the degree of each vertex where vertex numbers are 1, 2, 3,…n. The task is to identify whether it is a graph or a tree. It may be assumed that the graph is connected.

Examples:

```Input : 5
2 3 1 1 1
Output : Tree
Explanation : The input array indicates that
vertex one has degree 2, vertex
two has degree 3, vertices 3, 4
and 5 have degree 1.
1
/
2   3
/
4   5

Input : 3
2 2 2
Output : Graph
1
/
2 - 3
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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.

So basically we need to check if sum of all degrees is 2*(n-1) ore not.

## C++

 `// C++ program to check whether input degree ` `// sequence is graph or tree ` `#include ` `using` `namespace` `std; ` ` `  `// Function returns true for tree ` `// false for graph ` `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); ` `} ` ` `  `// Driver program to test above function ` `int` `main() ` `{ ` `    ``int` `n = 5; ` `    ``int` `degree[] = {2, 3, 1, 1, 1}; ` ` `  `    ``if` `(check(degree, n)) ` `        ``cout << ``"Tree"``; ` `    ``else` `        ``cout << ``"Graph"``; ` ` `  `    ``return` `0; ` `} `

## Java

 `// Java program to check whether input degree  ` `// sequence is graph or tree  ` `class` `GFG  ` `{ ` ` `  `    ``// Function returns true for tree  ` `    ``// false for graph  ` `    ``static` `boolean` `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); ` `    ``} ` ` `  `    ``// Driver code  ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``int` `n = ``5``; ` `        ``int` `degree[] = {``2``, ``3``, ``1``, ``1``, ``1``}; ` ` `  `        ``if` `(check(degree, n)) ` `        ``{ ` `            ``System.out.println(``"Tree"``); ` `        ``}  ` `        ``else`  `        ``{ ` `            ``System.out.println(``"Graph"``); ` `        ``} ` `    ``} ` `}  ` ` `  ` `  `// This code has been contributed  ` `// by 29AjayKumar `

## Python

 `# Python program to check whether input degree ` `# sequence is graph or tree ` `def` `check(degree, n): ` `     `  `    ``# Find sum of all degrees ` `    ``deg_sum ``=` `sum``(degree) ` `     `  `    ``# It is tree if sum is equal to 2(n-1) ` `    ``if` `(``2``*``(n``-``1``) ``=``=` `deg_sum): ` `        ``return` `True` `    ``else``: ` `        ``return` `False` `     `  `#main ` `n ``=` `5` `degree ``=` `[``2``, ``3``, ``1``, ``1``, ``1``]; ` `if` `(check(degree, n)): ` `    ``print` `"Tree"` `else``: ` `    ``print` `"Graph"`

## C#

// C# program to check whether input
// degree sequence is graph or tree
using System;

class GFG
{

// Function returns true for tree
// false for graph
static 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); } // Driver code public static void Main() { int n = 5; int[] degree = {2, 3, 1, 1, 1}; if (check(degree, n)) { Console.WriteLine("Tree"); } else { Console.WriteLine("Graph"); } } } // This code has been contributed // by Akanksha Rai [tabby title="PHP"]

 ` `

Output:

```Tree
```

Graph Graph