Ninguém diz: «O princípio que eu parti...», porque ninguém parte um princípio.
Dizemos, sim: «O princípio de que eu parti» = «o princípio do qual/donde eu parti. Do qual, donde ou de que é o complemento circunstancial de lugar donde, que exige a preposição de.
Em conclusão: o correcto é: «partir do princípio de que.»