I friend of mine fed this problem to Chat GPT o3. It found the formula for a(n) in about 2 minutes, and it included a proof of achievability that was very much like yours. Were you inspired by AI, or do great minds (yours and o3) simply think alike? I will post o3's proof next.

That is very impressive! I'm not sure I followed all of it, but what I got made sense. Having a strong theorem of directed graphs to work with certainly helps. And it was very satisfying to see the 7 color hedge cranked out!

Because I specified a closed loop hedge, my max is n-1 less than yours.

Yes. I would be very interested seeing a proof that the max is always attainable. Here’s the max: oeis.org/A382411

I was generalizing to "Every group of n shrubs must have at least n-1 colors". It was not clear to me that I could find solutions for the theoretical maximum lengths, so I was happy to discover an example for 5 colors, and (after burning much midnight silicon) for 6 colors. I have not attempted 7.

Excellent answer!! The original problems did call for examples, so thanks for following through. Particularly loved the rhombicuboctahedron. Have you thought about 5 or 6 colors?

Good research! Here's a graphic solution: deanbal.net/puz/candy.png