In a simple graph with $2m$ vertices and a unique perfect matching, prove that $|E(G)|$ is bounded by $m^2$.

81 Views Asked by At

I have been trying to solve this question, it was already asked but the response seems to have some issues.

The accepted answer implies that if a graph has a cycle of length 4, this implies that it has more than one perfect matching, but this is not true. I’m including a counter-example below, a graph with a cycle of length 4 but still with only one perfect matching: counter-example

1

There are 1 best solutions below

1
On BEST ANSWER

The answer that you have linked is correct. It does not state that a simple graph with a unique perfect matching has no $4$-cycles. Rather, it states that if $M$ is the unique perfect matching with $\{v_1,w_1\}$ and $\{v_2, w_2\}$ being two pairs in this matching, then not both of $v_1v_2$ and $w_1w_2$ can be edges. Indeed, this is because if they both were edges, you can swap the edges $v_1w_1$ and $v_2w_2$ with $v_1v_2$ and $w_1w_2$ in $M$.

On the other hand, in your example, none of the edges in the $4$-cycle are involved in $M$. There would only be a problem if you have a $4$-cycle with an opposite pair of edges in the $4$-cycle in $M$.