การพิสูจน์ประกอบไปด้วยสองส่วน คือ ส่วนแรกเป็นการพิสูจน์ว่าขั้นตอนวิธีนี้สร้างต้นไม้แบบทอดข้ามได้ ส่วนที่สองคือพิสูจน์ว่าต้นไม้ทอดข้ามดังกล่าวมีน้ำหนักรวมน้อยที่สุด

ต้นไม้ทอดข้าม

ให้ P เป็นกราฟเชื่อมโยงที่มีน้ำหนัก และให้ Y เป็นกราฟย่อยของ P ที่สร้างโดยขั้นตอนวิธีนี้ Y ไม่มีวัฏจักร มีหนึ่งต้นไม้ย่อย และไม่มีต้นไม้สองต้นที่แตกต่างกัน Y ไม่สามารถไม่เชื่อมโยงได้ เพราะ เส้นเชื่อมแรกที่พบจะเชื่อมสองจุดยอดใน Y แล้วจะถูกเพิ่มตามขั้นตอนวิธี ดังนั้น Y จึงเป็นต้นไม้แบบทอดข้ามของ P

ความต่ำสุด

เราจะแสดงว่าประพจน์ P เป็นจริงโดยใช้ อุปนัยเชิงคณิตศาสตร์ ถ้า F เป็นเซตของเส้นเชื่อมที่ถูกเลือกที่แต่ละระดับของขั้นตอนวิธี แล้วจะได้ต้นไม้แบบทอดข้ามน้อยที่สุดที่มี F อยู่ด้วย

• ชัดเจนว่า P เป็นจริงตั้งแต่เริ่มต้น เมื่อ F เป็นเซตว่าง ทุกต้นไม้แบบทอดข้ามน้อยที่สุดจะเป็นเช่นนั้น และถ้ามีอย่างน้อยหนึ่งเส้นเชื่อมก็จะเป็นต้นไม้แบบทอดข้ามน้อยที่สุดเพราะเป็นกราฟเชื่อมโยงที่มีน้ำหนัก
• สมมติให้ P เป็นจริงสำหรับบางเซตของเส้นเชื่อม F และให้ T เป็นต้นไม้แบบทอดข้ามน้อยที่สุดที่บรรจุ F ไว้ ถ้าเลือกเส้นเชื่อมถัดไป e ก็ยังอยู่ใน T ดังนั้น P เป็นจริงสำหรับ F + e มิฉะนั้น T + e จะมีวัฏจักร C และเส้นเชื่อมอื่น f ที่อยู่ใน C แต่ไม่อยู่ใน F (ถ้าไม่มีเส้นเชื่อม f เลยแล้ว e จะไม่อยู่เพิ่มเข้าไปใน F เพราะการกระทำนั้นจะทำให้เกิดวัฏจักร C) แล้ว T − f + e เป็นต้นไม้ และมีน้ำหนักเท่ากับ T เพราะ T เป็นมีน้ำหนักน้อยที่สุด และน้ำหนักของ f จะไม่น้อยไปกว่า e มิฉะนั้นขั้นตอนวิธีจะเลือก f แทน e ดังนั้น T − f + e คือต้นไม้แบบทอดข้ามน้อยที่สุด ที่มี F + e
• ดังนั้นจากอุปนัยเชิงคณิตศาสตร์จึงสรุปได้ว่า P เป็นจริง เมื่อ F เป็นต้นไม้ทอดข้าม