I have tried giving Gracie whole carrots but she won't go for it. I guess she is spoiled because of all the baby carrots she is accustomed to getting. I really don't know how effective a carrot would be in cleaning the teeth though if your dog likes it I guess it can't hurt.
Gracie loves her bully sticks and they are good for cleaning teeth though not for giving fresh breath.