Which of these graphs is guaranteed to have a perfect matching?
A path graph PnP_nPn where nnn is odd.
A cycle graph CnC_nCn where nnn is even.
A complete graph KnK_nKn where nnn is odd.
A star graph SnS_nSn for n>2n > 2n>2.