# [Python 3], 68 bytes

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

    f=lambda g:len({*sum(g,())})<2*len(g)and max(f(g-{k})for k in g)or g

[Try it online!][TIO-khbqb0ln]

[Python 3]: https://docs.python.org/3/
[TIO-khbqb0ln]: https://tio.run/##Jc3RDoIwDAXQX@ljS2oim/hg9GNmcJXACgFMNAvfPrfs6dzbPtzlt79ntSn5x@TCs3cgt@mlGJvtE1AYiQ66m6bchJz2ENwXPcopjgf5eYURBgWhnCQt66B7/kY8c0sMGVNo2VYuBVObrc1yV@j4mpco/QE "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.