What is the rating of the relay coil. I bet it is greater than what the Arduino pins can output reliably - the data sheet specs at 70 - 80mA for the 5V version which is 4 times more than the Mega is spec'd for.
What is the rating of the relay coil. I bet it is greater than what the Arduino pins can output reliably - the data sheet specs at 70 - 80mA for the 5V version which is 4 times more than the Mega is spec'd for.