Which one is correct?
I am a new graduate and have been teaching German for a few weeks now.
I am a newly graduate and ...
I can't decide whether to use "new" or "newly".
"new graduate" is correct.
'New' is an adjective which describes the noun, 'graduate'.
'Newly' is an adverb which would describe a verb, but in this case, you need the noun.
As Nishant has already said, the correct usage is new graduate because of the adjective/noun relationship. A sample phrase for newly graduated would be something like: