我觉得完全可以零基础入门,很多内容并未要求额外的知识能力。我自己证明过的定理中,有些证明非常长,但其实就是反证加归纳,只不过可能嵌套几层,看上去很复杂。著名如七桥问题的证明,好像也是除了推理再无其他,并无中学以上的知识点。我认为只需逻辑思维过硬,静得下心,就可以学好图论。另一方面,图论研究数学对象及其关系,这样的定位使得图论和整个数学都扯得上关系。因此如果要深入,代数几何拓扑组合都需要一定了解。
没什么特别的基础,但是建议和编程结合起来,会有帮住,