# [Python 3], 83 bytes

<!-- language-all: lang-python -->

    f=lambda g:len({j for i in g for j in i})==len(g)*2and g or max(f(g-{k})for k in g)

[Try it online!][TIO-khbppxes]

[Python 3]: https://docs.python.org/3/
[TIO-khbppxes]: https://tio.run/##JYvNDsIgEIRfZY@sWRML1oMJD4OpIP3ZNk0PGsKzI1tO30y@me13fFY2pXg7u@U1OAjP@c0qjeDXHSJEhnDGUWLMaK34gBfteKiuqsV9lVfhmqaMMp3OF5Ztj3xUk9SNOiSo0IKOTMNdoFszrRnqBT09MCOWPw "Python 3 – Try It Online"

Takes input as set. Recursively removes one item until there are no duplicate vertices. It then returns the set with the most items.