Perfect Matching via ∃ M ⊆ E

Prompt (Question • Data • Logic)

Question.
Does the bipartite graph G=(L,R,E) have a perfect matching?
Data.
L = {u1,u2,u3,u4}
R = {v1,v2,v3,v4}
E = { u1→v1, u1→v2, u2→v2, u2→v3, u3→v1, u3→v3, u3→v4, u4→v4 }
Logic (Second-Order).
∃ M ⊆ E. PerfectMatching(M) ∧ covers(L∪R)
We quantify over a subset of edges M; this is a genuine second-order witness.

Answer

—

Reason Why

—

Checks (at least 5)

  1. —

Diagnostics

No errors yet.