I am trying to write a divide & conquer algorithm for trees. For the divide step I need an algorithm that partitions a given undirected Graph G=(V,E) with n nodes and m edges into sub-trees by removing a node . All subgraphs should have the property that they don t contain more than n/2 nodes (the tree should be split as equal as possible). First I tried to recursively remove all leaves from the tree to find the last remaining node, then I tried to find the longest path in G and remove the middle node of it. The given graph below shows that both approaches don t work:
<img src="https://i.stack.imgur.com/qNbko.png" alt="Graph">
Is there some working algorithm that does what I want (returns the node H in the above case).