asked 2 years, 3 months ago

Reputation: 1

0

I want to know the conditions for a graph to become a tree.

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

Asked: 2 years, 3 months ago

Viewed: 713 times

Active: 2 years, 3 months ago