Does October first always fall on Monday the year after it fell on Sunday?

That is true only in regular years. When October 1st falls on a Sunday in the year before a leap year, in the leap year it falls on a Tuesday.