I understand that the Messiah must be a descendant of David but where does it say he must be a descendant of Solomon as well?
The Scriptures teach that the Messiah will inherit his lawful and legal right to kingship through the ancestry of his biological father. Explicit in this evidence is the fact that God's promised Messiah must be a male heir of not only David:
For thus says the Lord: There shall not be cut off to David a man to sit upon the throne of the house of Israel . . . . If you can break My covenant with the day and My covenant with the night, so that there should not be day and night in their season; then may also My covenant be broken with David My servant, that he should not have a son to reign upon his throne. . . . So will I multiply the seed of David My servant. (Jeremiah 33:17-22)
but specifically of Solomon as well:
When your [David's] days are fulfilled, and you shall sleep with your fathers, I will set up your seed after you, that shall proceed out of your body, and I will establish his kingdom. He shall build a house for My name, and I will establish the throne of his kingdom forever. I will be to him for a father, and he shall be to Me for a son; if he commits iniquity, I will chasten him with the rod of men, and with the stripes of the children of men, but My mercy shall not depart from him, as I took it from Saul, whom I put away before you. And your house and your kingdom shall be made sure forever before you: your throne shall be established forever. (2 Samuel 7:12-16; see also 1 Chronicles 17:11-14, 2 Chronicles 7:17-18)
And of all my sons--for the Lord has given me many sons--He has chosen Solomon my son to sit upon the throne of the kingdom of the Lord over Israel. And He said to me: "Solomon your son, he shall build My house and My courts; for I have chosen him to be for a son, and I will be to him for a father. And I will establish his kingdom forever, if he be constant to do My commandments and My ordinances, as at this day." (1 Chronicles 28:5-7)
And David the king said to all the congregation: "Solomon my son, who alone God has chosen. . . ." (1 Chronicles 29:1)
. . . as the Lord lives, who has established me [Solomon], and set me on the throne of my father, and who made me a house, as He promised. . . . (1 Kings 2:24)
In obedience to God's decision to establish Solomon as king the Scriptures state:
And all the princes, and the mighty men, and all the sons likewise of king David, submitted themselves to Solomon the king. (1 Chronicles 29:24)
God declares that under no circumstances would He take the throne away from Solomon as He took it from Saul.
If he [Solomon] commits iniquity I will chasten him with the rod of men, and with the stripes of the children of men, but My mercy shall not depart from him, as I took it from Saul . . . (2 Samuel 7:14-15).
How did God take the kingdom from Saul? The right to the kingship terminated with Saul's death. No son of Saul ever sat on or had a right to the throne. But Solomon's descendants, with the exception of one branch of the family, would never lose their right to the throne. The punishment for disobedience would be chastening at the hands of men but not the termination of the monarchical right. It is God's unconditional promise that the posterity of David, specifically that of Solomon, will possess the kingship forever. God assures that there will always be a male of paternal Solomonic descent with the right to reign upon David's throne.