-고도 (and -고, -고는, -고서)
It will help to try to understand the difference between -고, -고는, -고서, and -고도.
1. 밥을 먹고 숙제를 하기 시작했다 - No particular connotation. Do one thing and then another.
2. 밥을 먹고는 숙제를 하기 시작했다 - 는 separates the two parts more clearly - Do one thing first, and then ...
3. 밥을 먹고서 숙제를 하기 시작했다 - 서 is similar. It adds the sense of "being/ending up in the state" or "after that".
4. 밥을 먹고도 배가 고프다 - 도 expresses "even as/so/then". Eating should have quenched hunger, but it did not.
So we can say "I ate, but even then [even so] I was still hungry", the second part contradicting the first.
(밥을 먹고도 숙제를 하기 시작했다 wouldn't make any sense because there's no element of contradiction)
Another example:
- 온 종일 일을 하고도 이렇게 많이 남았다. (Worked all day but there's still so much left - GOOD)
- 온 종일 일을 하고 이렇게 많이 남았다. (Worked all day, and there's still so much left - ILLOGICAL)
- 온 종일 일을 하고는 이렇게 많이 남았다. (Worked all day and now there's still so much left - ILLOGICAL)
- 온 종일 일을 하고서 이렇게 많이 남았다. (Worked all day and after that there's still so much left - ILLOGICAL)
And here's a line from a song.
- 너를 사랑하고도 늘 외로운 나는 / 가눌 수 없는 슬픔에 목이 메이고 ...
(Even as I loved you I always felt lonely / Choking with a sadness that I couldn't bear ...)
Loving someone should normally dispel loneliness, but the speaker still felt lonely - a surprising, unexpected outcome.