B. Body Building
Author: Suhendry Effendy.
Prepared by: Suhendry Effendy, Felix Halim.
Problem: B – Body Building
The dumbbell graph (or sometimes refered as barbel graph) mentioned in the problem statement is a proper term in graph theory; we didn’t make up the term. Recognizing a dumbbell graph can be done in O(|E| + |V|).
Recall that a dumbbell graph is constructed by connecting two complete graph of the same size with a single edge. It means:
- |V| should be even;
- There should be |V|-2 nodes which degree is |V|/2-1;
- and exactly two nodes which degree is |V|/2.
The edge which connect the two complete graphs is also called “bridge” in graph theory, an edge which removal will cause the graph to be disconnected. Any dummbell graph should have those properties. However, having those properties doesn’t mean the graph is a dumbbell. For example, consider the following graph:
This graph has 6 nodes (#1), 4 nodes which degree is 2 (#2), and 2 nodes which degree is 3 (#3). It satisfies all three properties, but it is not a dumbbell graph – as you can see, there is no bridge in this graph.
Therefore, it is necessary to actually check whether the graph contains two disjoint complete graphs which are connected by a single edge. Simply pick one arbitrary node which degree is |V|/2-1, and check whether it forms a complete graph with all its neighbours; in other words, let a, a1, a2, …, ada be node a ∪ a’s neighbours, you have to check whether all those nodes form a complete graph. This can be done in O(|E| + |V|).
Depending on how you do the verification, checking the remaining nodes might not be needed (recall that there supposed to be two complete graphs). For example, if you already verify the previous three properties, then you only need to check one complete graph (as the remaining will also be a complete graph if the verification return true); otherwise, you might need to check the remaining nodes whether they also form a complete graph.
Note, in this write-up, I didn’t discuss the part where you should find the connected component first. I leave this to the reader as it is easier than checking the dumbbell graph.