# Questions

### How to check if a graph is a tree?

0

I want to know the conditions for a graph to become a tree. asked 2 years, 3 months ago
Reputation: 1

0

Facts:

• A tree is always a graph but a graph may or may not be a tree.
• A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any acyclic connected graph is a tree.

Condition for a graph to become a tree

• A tree with n vertices will always have n-1 edges, so if a graph has n-1 edges it is a tree.
``````    Total edges = n-1
``````
• As each edge contributes for 2 degrees, so for a graph to become a tree sum of degrees of all nodes equals 2(n-1).
``````    Sum of degrees of all nodes = 2(n-1)
``````

Code

``````#include<bits/stdc++.h>
using namespace std;

int main(){
int n,sum,num,i;
//Number of vertices
cin>>n;

sum=0;
for(i=0;i<n;++i){
// Degrees for all the vertices
cin>>num;
sum += num;
}

if(sum==2*(n-1)){
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
}

return 0;
}
`````` answered 2 years, 3 months ago
Reputation: 1