After that he studied mathematics and physics at the University of Vienna; his main teachers were Nikolaus Hofreiter and Edmund Hlawka.
Fleischner started his academic career as an assistant at the Technical University of Vienna.
One of his main achievements is the proof of the theorem according to which the square of every two-connected graph has a Hamiltonian cycle.
His friendship with the Austrian painter de:Robert Lettner resulted in a cooperation in which certain graphs were transformed into paintings called mutations.
During 2002-2007 he was Chairman of the Committee for Developing Countries of the European Mathematical Society (EMS-CDC).