I have to find which of the following values can be the degrees of an undirected graph with 6 vertices:
a) 3 2 2 2 3 3
b) 4 2 2 2 3 2
c) 5 2 2 2 0 3
d) 5 2 2 2 1 2
I only method I found is to try to draw the graph on a sheet of paper and then check if it is possible.
I just need a hint to start this problem, if possible, in other way than drawing each graph.
Well, you can proceed by elimination. I'm gonna try to explain without giving it all away.
Hint 1:
In an undirected graph, every edge that is counted on the degree of one node must also be counted in the degree of the other node to which it leads. For example, this list of degrees is possible:
0 1 0 0 1
because, clearly, there is an edge going from node 2 to node 5, i.e., it is counted twice, once in node 2 and once in node 5. On the contrary, this list of degrees is impossible:
0 1 0 1 1
Hint 2:
If the graph cannot have redundant edges (i.e., multiple edges going from the same source to the same destination), and that the edges cannot be looping back directly (i.e., source node and destination node are the same), then any one node cannot have a degree higher than the number of other nodes with a non-zero degree.
I tried not to spell out the answer too obviously... no sure if I succeeded.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.