parag776's blog

can we always form a graph with this condition?
By parag776, history, 15 months ago, In English

we have any arbitrary set of numbers such that the length of the set is greater than every number in the set and sum of all the numbers in the set is even, then this forms a graph with those numbers being the degree of the each vertex respectively in the graph. is always true?

I could not find the answer to it. maybe I did not look hard enough.

explanation with example:

suppose there is a set {4, 2, 4, 6, 2, 3, 1}

here every number in the set is less than 7 (length of the set) and sum of the numbers is 22 which is even, then this set can be converted to a graph of 7 vertices with those numbers as their degrees.

(a simple graph)

can someone Please answer.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
15 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

{2, 0, 0} there is no graph :)

→ Reply
»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Erdős–Gallai theorem is the answer.
Related blogpost

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can probably use a greedy approach for this. Simply sort the array in descending order. Also, maybe add n zeroes to the end of the array because it might make implementation a bit simpler. So now, all you have to do is for every number "num" in the array, reduce the next num numbers by 1. Then just loop through the entire array and check if any of the numbers are negative. If they are then there is no graph, otherwise there will be a graph.

Please consult me if you need more explanation.

→ Reply