There could easily be a bias error, but I said what I said simply because everything covered in the CS curriculum seems to also be present in the CE curriculum, but in the CE curriculum more is added. So I see the CE degree as a CS degree plus the essentials of an Electrical Engineering degree.
The advantages, if there are any, can definitely fade away after a few years of real experience, assuming everyone continues to better their knowledge, and those years aren't spent, as is typically the case, repeatedly re-implementing the same solution.
Or was those covered in your compiler course?
We covered graph theory in discrete math - it wasn't an independent topic - so I'm surprised that you didn't cover it in your discrete math courses. As I recall, first semester was more combinatorics and second was more graph theory, but I don't recall at this point.
Also, in reading the ACM curricula guidelines, I came across the comment "As is typical of most programs in engineering, this program has a smaller general education component than Curriculum A described in this appendix, with more hours devoted to computer engineering topics."
That is (and using your earlier terminology), a computer engineering degree is more specialized, while a computer science degree will include more non-CS courses and give a 'more versatile, open-ended' education. :)
In my career so far developing software for chemistry I've made heavy use of graph theory, formal language theory, and data structures that I learned while an undergraduate.
I don't have the same assessment as you in the advantage of a CE degree over a CS degree. I suspect there's a bias error, as you did not enter a field where a CS degree would have been more useful. Nor do I think that a CS degree is specializing, given the courses I took in operating systems, programming language theory, computer graphics, databases, etc. Of course, from my perspective "electrical design, hardware/chip design, embedded systems design" are all variations of the same thing, so it's a definite matter of perspective.
In any case, after 5 years or so in a career, the specific advantages of one background over the other get pretty weak.