 # Help needed for solving this problem based on graph

Given am array of N integers is it possible to design a simple graph of N vertices?.

A graph considered simple if it has no self-loop r multi-edges. The condition is that each element of array should be used exactly once for degrees of vertices of the graph.

Print Yes if graph can be designed other wise no.

INPUT

A single integer T, in the first line, denoting the no. of test cases.

For each test case first line is a single integer N, denoting the no. of elements of an array A.

The second line contains N space separated integers denoting the elements of an array.

OUTPUT

For each test case print “YES” or “NO” without quotes.

SAMPLE INPUT

3

2

1 1

3

1 2 1

3

1 1 1

SAMPLE OUTPUT

YES

YES

NO

Please write the problem clearly. What does each element of the array signify?

I think this can be solved as follows :

1. Since each element a[i] denotes the degree of the ith vertex we can say that the value of any a[i] can be at most n-1
2. Secondly, we need to make sure that the sum of all elements in the array (i.e sum of all degrees) is a even number

If the above 2 conditions are met, then print YES, otherwise print NO

The question clearly stated that the graph should be a simple graph meaning no multi-edges and hence the 1st condition is valid.

If u still have doubts about it, try drawing a simple graph where you keep the degree of a vertex > |V|-1. (U will end up with a multigraph)

Edit : my solution in code [here]
: https://pastebin.com/XGwDBFUK

@ronakchauhan

what you said is wrong,for example consider the following case

1

4

3 3 1 1

For this input your code will print YES,but the answer is no
edges will be like this

1 2

1 3

1 4

2 2

There is a self loop for node 2 and hence answer is NO

Ohh i get it @hruday968, thanks for pointing out!

After some googling I found that this problem is the graph realization problem
with slight variation. It can be solved using Erdős–Gallai theorem.

One way to solve this would be to sort the array in descending order and then apply the theorem

Everyone should know the programming language in every sense of knowledge.wedding photography Kerala and the team like this article so much.

@senbihan

It is the degree of each vertex.

@senbihan

I have updated the question look at it once more. Tell me if further clarification is needed.

@ronakchauhan

How to deal with multi-edges. I think the approach which you proposed will not be able to handle multi-edges.

I’ll give a hint for this problem For any graph G, SUM(Degree of each node) = 2 x Edges. Using this formula, you get the edges. So you have V,E. Is it possible to draw a Graph with V vertex and E edges, satisfying your constraints.

@hruday968

What would be the correct way then.