I am talking mostly from my own experience (from two or three European universities). A lot of my undergraduate CS programme was very mathematics heavy with a lot of focus on proofs (a lot of calculus, linear algebra, discrete mathematics, graph theory, algebra, even set theory for some, first order and predicate logic) and then of course a lot of foundational CS subjects like automata theory, basic datastructures, crypto, .... I would argue that proper rigorous proofs and thinking are maybe easier taught on the example of calculus or set theory rather than graph theory (I am not talking about discrete mathematics such as combinatorics without much of graphs, etc.). In graph theory, you often resort to doing proofs "by drawing" assuming that a skilled reader would be able to fill in the dots in a formal manner. That said, it's just my opinion and your course may have ways around it.