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

• Difficulty Level : Basic
• Last Updated : 05 Jul, 2022

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```

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) or not.

Implementation:

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

## PHP

 ``

Output

`Tree`

This article is contributed by Ayush Khanduri. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

My Personal Notes arrow_drop_up