Return to Answer

Suppose that $X$ and $Y$ are finite undirected graphs such that the set of arcs of $X$ and $Y$ have the same cardinal and $f$ is a weak equivalence: firstly we remark that $f$ induces a bijection between the sets of arcs of $X$ and $Y$. Let $b$ be an arc of $Y$, there exists a maximum matching $p\sum_JA_U^J\rightarrow Y$ whose image contains $b$, we can lift $p$ to $q:\sum_JA_U^j\rightarrow X$ such that $p=f\circ q$, this implies that there exists an arc $a$ of $X$ such that $f(a)=b$. Since $f$ is surjective on arcs and the cardinals of the set of arcs of $X$ and $Y$ are equal, we conclude that $f$ induces a bijection between the sets of arcs of $X$ and $Y$. Let $g:V_U\rightarrow Y$, there exists $arcs $a,a'$ of $X$ such that the image of $(a,a')$ the subgraph of $X$ which is the union of $a$ and $a'$ by $f$ is $g(V_U)$, suppose that $a,a'$ do not have a common vertex, there exists a maximal matching $p\sum_JA_U^j\rightarrow X$ whose image contains $(a,a')$, but $f\circ p$ is not a matching: contradiction, since we have supposed that $f$ induces a map well defifined on maximal matchings. This implies that $g$ can be lifted to $X$ and $Hom(V_U,X)\rightarrow Hom(V_U,Y)$ induced by $f$ is surjective. This map is also injective since $f$ is induces a bijection on arcs.

Suppose that $X$ and $Y$ are finite undirected graphs such that the set of arcs of $X$ and $Y$ have the same cardinal and $f$ is a weak equivalence: firstly we remark that $f$ induces a bijection between the sets of arcs of $X$ and $Y$. Let $b$ be an arc of $Y$, there exists a maximum matching $p\sum_JA_U^J\rightarrow Y$ whose image contains $b$, we can lift $p$ to $q:\sum_JA_U^j\rightarrow X$ such that $p=f\circ q$, this implies that there exists an arc $a$ of $X$ such that $f(a)=b$. Since $f$ is surjective on arcs and the cardinals of the set of arcs of $X$ and $Y$ are equal, we conclude that $f$ induces a bijection between the sets of arcs of $X$ and $Y$. Let $g:V_U\rightarrow Y$, there exists arcs $a,a'$ of $X$ such that the image of $(a,a')$ the subgraph of $X$ which is the union of $a$ and $a'$ by $f$ is $g(V_U)$, suppose that $a,a'$ do not have a common vertex, there exists a maximal matching $p\sum_JA_U^j\rightarrow X$ whose image contains $(a,a')$, but $f\circ p$ is not a matching: contradiction, since we have supposed that $f$ induces a map well defifined on maximal matchings. This implies that $g$ can be lifted to $X$ and $Hom(V_U,X)\rightarrow Hom(V_U,Y)$ induced by $f$ is surjective. This map is also injective since $f$ is induces a bijection on arcs.

Suppose that $X$ and $Y$ are finite undirected graphs such that the set of arcs of $X$ and $Y$ have the same cardinal and $f$ is a weak equivalence: firstly we remark that $f$ induces a bijection between the sets of arcs of $X$ and $Y$. Let $b$ be an arc of $Y$, there exists a maximum matching $p\sum_JA_U^J\rightarrow Y$ whose image contains $b$, we can lift $p$ to $q:\sum_JA_U^j\rightarrow X$ such that $p=f\circ q$, this implies that there exists an arc $a$ of $X$ such that $f(a)=b$. Since $f$ is surjective on arcs and the cardinals of the set of arcs of $X$ and $Y$ are equal, we conclude that $f$ induces a bijection between the sets of arcs of $X$ and $Y$. Let $g:V_U\rightarrow Y$, there exists $arcs $a,a'$ of $X$ such that the image of $(a,a')$ the subgraph of $X$ which is the union of $a$ and $a'$ by $f$ is $g(V_U)$, suppose that $a,a'$ do not have a common vertex, there exists a maximal matching $p\sum_JA_U^j\rightarrow X$ whose image contains $(a,a')$, but $f\circ p$ is not a matching: contradiction, since we have supposed that $f$ induces a map well defifined on maximal matchings.

Suppose that $X$ and $Y$ are finite undirected graphs such that the set of arcs of $X$ and $Y$ have the same cardinal and $f$ is a weak equivalence: firstly we remark that $f$ induces a bijection between the sets of arcs of $X$ and $Y$. Let $b$ be an arc of $Y$, there exists a maximum matching $p\sum_JA_U^J\rightarrow Y$ whose image contains $b$, we can lift $p$ to $q:\sum_JA_U^j\rightarrow X$ such that $p=f\circ q$, this implies that there exists an arc $a$ of $X$ such that $f(a)=b$. Since $f$ is surjective on arcs and the cardinals of the set of arcs of $X$ and $Y$ are equal, we conclude that $f$ induces a bijection between the sets of arcs of $X$ and $Y$. Let $g:V_U\rightarrow Y$, there exists $arcs $a,a'$ of $X$ such that the image of $(a,a')$ the subgraph of $X$ which is the union of $a$ and $a'$ by $f$ is $g(V_U)$, suppose that $a,a'$ do not have a common vertex, there exists a maximal matching $p\sum_JA_U^j\rightarrow X$ whose image contains $(a,a')$, but $f\circ p$ is not a matching: contradiction, since we have supposed that $f$ induces a map well defifined on maximal matchings. This implies that $g$ can be lifted to $X$ and $Hom(V_U,X)\rightarrow Hom(V_U,Y)$ induced by $f$ is surjective. This map is also injective since $f$ is induces a bijection on arcs.

In , I have described a method to generate closed models in a category: closed models defined by counting:

We consider the closed model $(Fib,Cof,W)$ defined by counting the objects $A_U$ and $V_U$ of $UGph$.

{\it A morphism $f:X\rightarrow Y$ between finite undirected graphs is a weakly equivalence between $X$ and $Y$ for the closed model defined by counting $A_U$ and $V_U$ if and only if it induces a bijection between the maximum matchings of $X$ and $Y$.}

Now we show that $f$ induces a surjection between the sets of maximum matchings of $X$ and $Y$. Let $p_Y:\sum_JA_U^j\rightarrow Y$ be a perfect matching. Since $f$ is defined by counting $A_U$ and $V_U$, it induces a bijection between the sets $Ar(X)$ and $Arc(Y)$ of arcs of $X$ and $Y$. We can define the morphism $p_X:\sum_J A_U^j\rightarrow X$ such that the restriction $p_X^j$ of $p_X$ to $A_U^j$ is the unique morphism $p^j_X:A_U^j\rightarrow X$ such that $p_Y^j=f\circ p_X^j$, $p_X$ is a maximum matching:

We have shown that a weak equivalence induces a bijection between maximal matching. The converse is also true, that is a morphism which induces a bijection between maximal matchings is a weak equivalence.

In th reference, I have described a method to generate closed models in a category: closed models defined by counting:

We consider the closed model $(Fib,Cof,W)$ defined by counting the object $V_U$ of $UGph$.

{\it Let $X$ and $Y$ be finite graphs, a weak equivalence $f:X\rightarrow Y$ for the closed model defined by counting $V_U$ induces a bijection between the maximum matchings of $X$ and $Y$. Conversely, if the cardinal of the set of arcs of $X$ and $Y$ are equal, then a morphism $f:X\rightarrow Y$ which induces a bijection between the maximal matchings of $X$ and $Y$ is a weak equivalence.}

Now we show that $f$ induces a surjection between the sets of maximum matchings of $X$ and $Y$. Let $p_Y:\sum_JA_U^j\rightarrow Y$ be a perfect matching. Since $f$ is defined by counting   $V_U$, it induces a bijection between the sets $Ar(X)$ and $Arc(Y)$ of arcs of $X$ and $Y$. We can define the morphism $p_X:\sum_J A_U^j\rightarrow X$ such that the restriction $p_X^j$ of $p_X$ to $A_U^j$ is the unique morphism $p^j_X:A_U^j\rightarrow X$ such that $p_Y^j=f\circ p_X^j$, $p_X$ is a maximum matching:

Suppose that $X$ and $Y$ are finite undirected graphs such that the set of arcs of $X$ and $Y$ have the same cardinal and $f$ is a weak equivalence: firstly we remark that $f$ induces a bijection between the sets of arcs of $X$ and $Y$. Let $b$ be an arc of $Y$, there exists a maximum matching $p\sum_JA_U^J\rightarrow Y$ whose image contains $b$, we can lift $p$ to $q:\sum_JA_U^j\rightarrow X$ such that $p=f\circ q$, this implies that there exists an arc $a$ of $X$ such that $f(a)=b$. Since $f$ is surjective on arcs and the cardinals of the set of arcs of $X$ and $Y$ are equal, we conclude that $f$ induces a bijection between the sets of arcs of $X$ and $Y$. Let $g:V_U\rightarrow Y$, there exists $arcs $a,a'$ of $X$ such that the image of $(a,a')$ the subgraph of $X$ which is the union of $a$ and $a'$ by $f$ is $g(V_U)$, suppose that $a,a'$ do not have a common vertex, there exists a maximal matching $p\sum_JA_U^j\rightarrow X$ whose image contains $(a,a')$, but $f\circ p$ is not a matching: contradiction, since we have supposed that $f$ induces a map well defifined on maximal matchings.