1.
Introduction
2.
Problem Statement
2.1.
Example
2.1.1.
Input
2.1.2.
Output
2.1.3.
Input
2.1.4.
Output
2.2.
Explanation
3.
Approach
4.
Implementation in C++
4.1.
Output
5.
Implementation in Java
5.1.
Output
6.
Implementation in Python
6.1.
Output
7.
Complexity
7.1.
Time Complexity
7.2.
Space complexity
8.
8.1.
What specific point distinguishes a tree from a graph?
8.2.
What are storage structures for graphs?
8.3.
What use cases does graph DS have?
8.4.
What purpose do graph algorithms serve?
8.5.
What is a tree, and what is its type?
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

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

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

## Introduction

In this article, we will check whether given degrees of vertices represent a Graph or Tree.

Before that, I will take you to the introduction of graph and tree.

tree is a discrete structure depicting the interactions between different parts or nodes in a hierarchy. Each parent has no more than two offspring in a binary tree.

graph is a visual representation of a collection of things where some object pairs are linked together. Vertices are the points used to depict related items, while edges are the connections between them.

## Problem Statement

Given that there are n vertices, each of which has a degree of 1, 2, 3, etc., Identifying a graph or tree is the problem at hand. The graph might be thought of as connected.

### Example

#### Input

``````5
1 1 1 3 2``````

#### Output

``Tree``

#### Input

``````3
3 3 3``````

#### Output

``Graph``

### Explanation

Vertex one has a degree of 2, while vertex two has a degree of 3, vertices 1, 3, and 2 have a degree 1, and so on.

In the other hand, vertex one, two and three all have 2 so,

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Approach

The number of edges entering or exiting a vertex determines its degree. The characteristics of trees make it easy to accomplish this.

• While graphs can contain cycles, trees are connected and do not.

• There is no such restriction for a graph, but a tree has exactly n-1 edges.

• The input graph is taken to be connected. It takes at least n-1 edges to connect n nodes. Each edge will be tallied twice if all the degrees are added.

If we add all the degrees, each edge will be counted twice. As a result, The total of all degrees for a tree with n vertices and n - 1 edge should equal 2 *(n â€“ 1). For further information, please see Handshaking Lemma.

In essence, we must determine whether the sum of all degrees is 2*(n-1) or not.

## Implementation in C++

``````// Checks whether the input degree sequence is a graph or a tree in C++.
#include<iostream>
using namespace std;

// The function returns either true for trees or false for graphs.
bool check(int degree[], int n)
{
// Fetching sum of all degrees
int sum = 0;
for (int i = 0; i < n; i++)
sum += degree[i];

// If the sum is 2(n-1), the graph is a tree
return (2*(n-1) == sum);
}

// programme for testing the above functionality
int main()
{
int n = 5;
int degree[] = {1, 1, 1, 3, 2};

if (check(degree, n))
cout << "Tree";
else
cout << "Graph";

return 0;
}``````

#### Output

``Tree``

## Implementation in Java

``````// Checks whether the input degree sequence is a graph or a tree in java.
class Fetch
{

// The function returns either true for trees or false for graphs.
static boolean check(int degree[], int n)
{
// Fetching sum of all degrees
int sum = 0;
for (int i = 0; i < n; i++)
{
sum += degree[i];
}

// If the sum is 2(n-1), the graph is a tree
return (2 * (n - 1) == sum);
}

// programme for testing the above functionality
public static void main(String[] args)
{
int n = 5;
int degree[] = {1, 1, 1, 3, 2};

if (check(degree, n))
{
System.out.println("Tree");
}
else
{
System.out.println("Graph");
}
}
}``````

#### Output

``Tree  ``

## Implementation in Python

``````#  Checks whether the input degree sequence is a graph or a tree in C++.
def check(degree, n):

# Fetching sum of all degrees
sum = sum(degree)

# If the sum is 2(n-1), the graph is a tree
if (2*(n-1) == sum):
return True
else:
return False

#programme for testing the above functionality
n = 5
degree = [1, 1, 1, 3, 2];
if (check(degree, n)):
print "Tree"
else:
print "Graph"``````

#### Output

``Tree``

## Complexity

### Time Complexity

O(N): where n is the size of array.

Reason: As we are fetching the sum of degrees in the program so, we are using for loop, which iterates from 0 to n.

### Space complexity

O(N): where n is the size of array.

Reason: As we are fetching the sum of degrees in the program so, we are using for loop, which requires an array of size n.
Check out this problem - Largest BST In Binary Tree

### What specific point distinguishes a tree from a graph?

There are vertices/nodes and edges in a graph. There are many nodes and edges in a tree. There is no single node in the graph that is the root. There is a special node in a tree called the root.

### What are storage structures for graphs?

A graph is a type of data structure where information is stored among numerous groups of connected edges (paths) and vertices (nodes). Many Nodes and Edges make up the graph data structure. Vertices and nodes must both be finite.

### What use cases does graph DS have?

Application in defining the software applications' computational flow. It is used to create transportation systems in Google Maps. In Google Maps, the node is the intersection of two or more roads, and the edge is the route that connects two nodes.

### What purpose do graph algorithms serve?

In order to depict graphs as networks, such as flights, the Internet's connectivity, or Facebook's social network connectedness, graph algorithms are utilised. They are frequently used to create networks in NLP and machine learning.

### What is a tree, and what is its type?

A particular kind of data structure used to represent hierarchical data is a tree. Nodes and edges make up the nonlinear structure. The complexity rises with the size of the data for the different kinds of data structures that carry out operations in a linear data structure.

## Conclusion

We have checked whether given degrees of vertices represent a Graph or Tree by implementation with three different programming languages. If you want to master Graph and Tree, please check the following articles: