Member Avatar for Fame95

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.

Edited by Fame95
  • 2 Contributors
  • 1 Reply
  • 275 Views
  • 1 Hour Discussion Span
  • Latest Post Latest Post by mike_2000_17
Member Avatar for mike_2000_17

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.