# 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

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 –

- Tree is
**connected**and has**no cycles**while graphs can have cycles. - Tree has exactly
**n-1**edges while there is no such constraint for graph. - 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<bits/stdc++.h>` `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

`<?php` `// PHP program to check whether input` `// degree sequence is graph or tree` `// Function returns true for tree` `// false for graph` `function` `check(&` `$degree` `, ` `$n` `)` `{` ` ` `// Find sum of all degrees` ` ` `$deg_sum` `= 0;` ` ` `for` `(` `$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` `$n` `= 5;` `$degree` `= ` `array` `(2, 3, 1, 1, 1);` `if` `(check(` `$degree` `, ` `$n` `))` ` ` `echo` `"Tree"` `;` `else` ` ` `echo` `"Graph"` `;` `// This code is contributed by` `// Shivi_Aggarwal` `?>` |

**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.