Teori graf merupakan bagian dari mata kuliah matematika diskrit yang mencakup konsep teori graf. Tujuan mengajarkan teori graf di jenjang pendidikan tinggi untuk memahami konsep Graf melibatkan kemampuan memecahkan masalah yang kompleks dan mengajarkan berpikir kritis bagi mahasiswa. Salah satu topik yang sering menjadi fokus dalam pembelajaran ini yaitu Graf Euler. Pemahaman tentang Graf Euler melibatkan keterampilan kritis dalam pemikiran dan konstruksi bukti matematis. Penelitian ini dilakukan dengan menggunakan perspektif Toulmin, yang merupakan teori tentang konstruksi bukti matematis. Teori ini menggambarkan bahwa konstruksi bukti matematis terdiri dari klaim, data, penjelasan, kualifikasi, dan rebuttal. Subjek dalam penelitian ini yaitu mahasiswa aktif Program Studi Pendidikan Matematika Universitas PGRI Adi Buana Surabaya angkatan 2022 yang aktif mengampu mata kuliah matematika diskrit. Tujuan dari penelitian ini untuk mengeksplorasi konstruksi bukti matematis yang dilakukan oleh mahasiswa dalam menyelesaikan soal Euler. Berdasarkan hasil analisis dalam penelitian ini subjek mampu menyelesaikan soal dengan memenuhi perspektif Toulmin, kedua subjek sudah mampu menjelaskan dari apa yang sudah dikerjakan berdasarkan hasil wawancara, yang artinya subjek sudah mampu mengeksplor konstruksi bukti matematis soal Graf Euler berdasarkan kerangka perspektif Toulmin. Rekomendasi dari hasil penelitian ini, untuk perpekstif Toulmin bisa diterapkan pada penerapan soal Graf Hamilton.