Uninstall / remove a Homebrew package including all its dependencies
By the end of 2020, the Homebrew team added a simple command brew autoremove to remove all unused dependencies.
First, uninstall the package:
brew uninstall <package>
Then, remove all the unused dependencies:
brew autoremove
EDIT:
It looks like the issue is now solved using an external command called brew rmdeps or brew rmtree.
To install and use, issue the following commands:
$ brew tap beeftornado/rmtree
$ brew rmtree <package>
See the above link for more information and discussion.
[EDIT] see the new command brew autoremove in https://stackoverflow.com/a/66719581/160968
Original answer:
It appears that currently, there's no easy way to accomplish this.
However, I filed an issue on Homebrew's GitHub page, and somebody suggested a temporary solution until they add an exclusive command to solve this.
There's an external command called brew leaves which prints all packages that are not dependencies of other packages.
If you do a logical and on the output of brew leaves and brew deps <package>, you might just get a list of the orphaned dependency packages, which you can uninstall manually afterwards. Combine this with xargs and you'll get what you need, I guess (untested, don't count on this).
EDIT: Somebody just suggested a very similar solution, using join instead of xargs:
brew rm FORMULA
brew rm $(join <(brew leaves) <(brew deps FORMULA))
See the comment on the issue mentioned above for more info.