|
12
|
|
edited Aug 26 2011 at 7:57 |
I'd say the Tutte-Berge formula, which is a wonderful result that tells you (almost) everything you want to know about matchings in graphs. Although there are many proofs of this theorem, there is a beautiful proof for free using matroids. Strictly speaking, there is a proof for free of Gallai's Lemma (from which Tutte-Berge follows easily).
Gallai's Lemma.
Let $G$ be a connected graph such that $\nu(G-x)=\nu(G)$, for all $x \in V(G)$. Then $|V(G)|$ is odd and def$(G)=1.$
Remark: $\nu(G)$ is the size of a maximum maximum matching of $G$, and def$(G)$ denotes the number of vertices of $G$ not covered by a maximum matching.
Proof for free.
In any matroid $M$ define the relation $x \sim y$ to mean $r(x)=r(y)=1$ and $r({x,y})=1$ or if $x=y$. (Here, $r$ is the rank function of $M$). We say that $x \sim^* y$ if and only if $x \sim y$ in the dual of $M$. It is trivial to check that $\sim$ (and hence also $\sim^*$) defines an equivalence relation on the ground set of $M$.
Now let $G$ satisfy the hypothesis of Gallai's Lemma and let $M(G)$ be the matching matroid of $G$. By hypothesis, $M(G)$ does not contain any co-loops. Therefore, if $x$ and $y$ are adjacent vertices we clearly have $x \sim^* y$. But since $G$ is connected, this implies that $V(G)$ consists of a single $\sim^*$ equivalence class. In particular, $V(G)$ has co-rank 1, and so def$(G)$=1, as required.
Edit. For completeness, I decided to include the derivation of Tutte-Berge from Gallai's lemma. Choose $X \subset V(G)$ maximal such that def$(G-X) -|X|=$ def$(G)$. By maximality, every component of $G-X$ satisfies the hypothesis in Gallai's lemma. Applying Gallai's lemma to each component, we see that $X$ gives us equality in the Tutte-Berge formula.
|
|
|
|
|
11
|
|
edited May 4 2011 at 1:30 |
I'd say the Tutte-Berge formula, which is a wonderful result that tells you (almost) everything you want to know about matchings in graphs. Although there are many proofs of this theorem, there is a beautiful proof for free using matroids. Strictly speaking, there is a proof for free of Gallai's Lemma (from which Tutte-Berge follows easily).
Gallai's Lemma.
Let $G$ be a connected graph such that def$(G-x)=$ def$(G)$, $\nu(G-x)=\nu(G)$, for all $x \in V(G)$. Then $|V(G)|$ is odd and def$(G)=1.$
Remark: $\nu(G)$ is the size of a maximum maximum of $G$, and def$(G)$ denotes the number of vertices of $G$ not covered by a maximum matching.
Proof for free.
In any matroid $M$ define the relation $x \sim y$ to mean $r(x)=r(y)=1$ and $r({x,y})=1$ or if $x=y$. (Here, $r$ is the rank function of $M$). We say that $x \sim^* y$ if and only if $x \sim y$ in the dual of $M$. It is trivial to check that $\sim$ (and hence also $\sim^*$) defines an equivalence relation on the ground set of $M$.
Now let $G$ satisfy the hypothesis of Gallai's Lemma and let $M(G)$ be the matching matroid of $G$. By hypothesis, $M(G)$ does not contain any co-loops. Therefore, if $x$ and $y$ are adjacent vertices we clearly have $x \sim^* y$. But since $G$ is connected, this implies that $V(G)$ consists of a single $\sim^*$ equivalence class. In particular, $V(G)$ has co-rank 1, and so def$(G)$=1, as required.
Edit. For completeness, I decided to include the derivation of Tutte-Berge from Gallai's lemma. Choose $X \subset V(G)$ maximal such that def$(G-X) -|X|=$ def$(G)$. By maximality, every component of $G-X$ satisfies the hypothesis in Gallai's lemma. Applying Gallai's lemma to each component, we see that $X$ gives us equality in the Tutte-Berge formula.
|
|
|
|
|
10
|
|
edited May 4 2011 at 1:08 |
I'd say the Tutte-Berge formula, which is a wonderful result that tells you (almost) everything you want to know about matchings in graphs. Although there are many proofs of this theorem, there is a beautiful proof for free using matroids. Strictly speaking, there is a proof for free of Gallai's Lemma (from which Tutte-Berge follows easily).
Gallai's Lemma.
Let $G$ be a connected graph such that def$(G-x)=$ def$(G)$, for all $x \in V(G)$. Then $|V(G)|$ is odd and def$(G)=1.$
Remark: def$(G)$ denotes the number of vertices of $G$ not covered by a maximum matching.
Proof for free.
In any matroid $M$ define the relation $x \sim y$ to mean $r(x)=r(y)=1$ and $r({x,y})=1$ or if $x=y$. (Here, $r$ is the rank function of $M$). We say that $x \sim^* y$ if and only if $x \sim y$ in the dual of $M$. It is trivial to check that $\sim$ (and hence also $\sim^*$) defines an equivalence relation on the ground set of $M$.
Now let $G$ satisfy the hypothesis of Gallai's Lemma and let $M(G)$ be the matching matroid of $G$. By hypothesis, $M(G)$ does not contain any co-loops. Therefore, if $x$ and $y$ are adjacent vertices we clearly have $x \sim^* y$. But since $G$ is connected, this implies that $V(G)$ consists of a single $\sim^*$ equivalence class. In particular, $V(G)$ has co-rank 1, and so def$(G)$=1, as required.
Edit. For completeness, I decided to include the derivation of Tutte-Berge from Gallai's lemma. Choose $X \subset V(G)$ maximal such that def$(G-X)=$ def$(G-X) -|X|=$ def$(G)$. By maximality, every component of $G-X$ satisfies the hypothesis in Gallai's lemma. Applying Gallai's lemma to each component, we see that $X$ gives us equality in the Tutte-Berge formula.
|
|
|
|
9
|
|
edited May 3 2011 at 23:42 |
I'd say the Tutte-Berge formula, which is a wonderful result that tells you (almost) everything you want to know about matchings in graphs. Although there are many proofs of this theorem, there is a beautiful proof for free using matroids. Strictly speaking, there is a proof for free of Gallai's Lemma (from which Tutte-Berge follows easily).
Gallai's Lemma.
Let $G$ be a connected graph such that def$(G-x)=$def$(G)$def$(G-x)=$ def$(G)$, for all $x \in V(G)$. Then $|V(G)|$ is odd and def$(G)=1.$
Remark: def$(G)$ denotes the number of vertices of $G$ not covered by a maximum matching.
Proof for free.
In any matroid $M$ define the relation $x \sim y$ to mean $r(x)=r(y)=1$ and $r({x,y})=1$ or if $x=y$. (Here, $r$ is the rank function of $M$). We say that $x \sim^* y$ if and only if $x \sim y$ in the dual of $M$. It is trivial to check that $\sim$ (and hence also $\sim^*$) defines an equivalence relation on the ground set of $M$.
Now let $G$ satisfy the hypothesis of Gallai's Lemma and let $M(G)$ be the matching matroid of $G$. By hypothesis, $M(G)$ does not contain any co-loops. Therefore, if $x$ and $y$ are adjacent vertices we clearly have $x \sim^* y$. But since $G$ is connected, this implies that $V(G)$ consists of a single $\sim^*$ equivalence class. In particular, $V(G)$ has co-rank 1, and so def$(G)$=1, as required.
Edit. For completeness, I decided to include the derivation of Tutte-Berge from Gallai's lemma. Choose $X \subset V(G)$ maximal such that def$(G-X)=$ def$(G)$. By maximality, every component of $G-X$ satisfies the hypothesis in Gallai's lemma. Applying Gallai's lemma to each component, we see that $X$ gives us equality in the Tutte-Berge formula.
|
|
|
|
|
8
|
|
edited May 3 2011 at 23:02 |
I'd say the Tutte-Berge formula, which is a wonderful result that tells you (almost) everything you want to know about matchings in graphs. Although there are many proofs of this theorem, there is a beautiful proof for free using matroids. Strictly speaking, there is a proof for free of Gallai's Lemma (from which Tutte-Berge follows easily).
Gallai's Lemma.
Let $G$ be a connected graph such that def$(G-x)=$def$(G)$, for all $x \in V(G)$. Then $|V(G)|$ is odd and def$(G)=1.$
Remark: def$(G)$ denotes the number of vertices of $G$ not covered by a maximum matching.
Proof for free.
In any matroid $M$ define the relation $x \sim y$ to mean $r(x)=r(y)=1$ and $r({x,y})=1$ or if $x=y$. (Here, $r$ is the rank function of $M$). We say that $x \sim^* y$ if and only if $x \sim y$ in the dual of $M$. It is trivial to check that $\sim$ (and hence also $\sim^*$) defines an equivalence relation on the ground set of $M$.
Now let $G$ satisfy the hypothesis of Gallai's Lemma and let $M(G)$ be the matching matroid of $G$. By hypothesis, $M(G)$ does not contain any co-loops. FurthermoreTherefore, if $x$ and $y$ are adjacent vertices we clearly have $x \sim^* y$. But since $G$ is connected, this implies that $V(G)$ consists of a single $\sim^*$ equivalence class. ThusIn particular, $V(G)$ has co-rank 1, and so def$(G)$=1, as required.
|
|
|
|
|
7
|
|
edited Mar 22 2010 at 16:32 |
I'd say the Tutte-Berge formula, which is a wonderful result that tells you (almost) everything you want to know about matchings in graphs. Although there are many proofs of this theorem, there is a beautiful proof for free using matroids. Strictly speaking, there is a proof for free of Gallai's Lemma (from which Tutte-Berge follows easily).
Gallai's Lemma.
Let $G$ be a connected graph such that def$(G-x)=$def$(G)$, for all $x \in V(G)$. Then $|V(G)|$ is odd and def$(G)=1.$
Remark: def$(G)$ denotes the number of vertices of $G$ not covered by a maximum matching.
Proof for free.
In any matroid $M$ define the relation $x \sim y$ to mean $r(x)=r(y)=1$ and $r({x,y})=1$ or if $x=y$. (Here, $r$ is the rank function of $M$). We say that $x \sim^* y$ if and only if $x \sim y$ in the dual of $M$. It is trivial to check that $\sim$ (and hence also $\sim^*$) defines an equivalence relation on the ground set of $M$.
Now let $G$ satisfy the hypothesis of Gallai's Lemma and let $M(G)$ be the matching matroid of $G$. By hypothesis, $M(G)$ does not contain any co-loops. Furthermore, if $x$ and $y$ are adjacent vertices we clearly have $x \sim^* y$. But since $G$ is connected, this implies that $V(G)$ consists of a single $\sim^*$ equivalence class. Thus, def$(G)$=1, as required.
|
|
|
|
|
6
|
|
edited Feb 23 2010 at 16:23 |
I'd say the Tutte-Berge Formulaformula, which is a wonderful result that tells you (almost) everything you want to know about matchings in graphs. Although there are many proofs of this theorem, there is a beautiful proof for free using matroids. Strictly speaking, there is a proof for free of Gallai's Lemma (from which Tutte-Berge follows easily).
Gallai's Lemma.
Let $G$ be a connected graph such that def$(G-x)=$def$(G)$, for all $x \in V(G)$. Then $|V(G)|$ is odd and def$(G)=1.$
Remark: def$(G)$ denotes the number of vertices of $G$ not covered by a maximum matching.
Proof for free.
In any matroid $M$ define the relation $x \sim y$ to mean $r(x)=r(y)=1$ and $r({x,y})=1$ or if $x=y$. (Here, $r$ is the rank function of $M$). We say that $x \sim^* y$ if and only if $x \sim y$ in the dual of $M$. It is trivial to check that $\sim$ (and hence also $\sim^*$) defines an equivalence relation on the ground set of $M$.
Now let $G$ satisfy the hypothesis of Gallai's Lemma and let $M(G)$ be the matching matroid of $G$. By hypothesis, $M(G)$ does not contain any co-loops. Furthermore, if $x$ and $y$ are adjacent vertices we clearly have $x \sim^* y$. But since $G$ is connected, this implies that $V(G)$ consists of a single $\sim^*$ equivalence class. Thus, def$(G)$=1, as required.
|
|
|
|
|
5
|
|
edited Feb 23 2010 at 2:37 |
I'd say the Tutte-Berge Formula, which is a wonderful result that tells you (almost) everything you want to know about matchings in graphs. Although there are many proofs of this theorem, there is a beautiful proof for free using matroids. Strictly speaking, there is a proof for free of Gallai's Lemma (from which Tutte-Berge follows easily).
Gallai's Lemma. Let $G$ be a connected graph such that def$(G-x)=$def$(G)$, for all $x \in V(G)$. Then $|V(G)|$ is odd and def(G)=1.def$(G)=1.$
Remark: def$(G)$ denotes the number of vertices of $G$ not covered by a maximum matching.
Proof for free.
In any matroid $M$ define the relation $x \sim y$ to mean $r(x)=r(y)=1$ and $r({x,y})=1$ or if $x=y$. (Here, $r$ is the rank function of $M$). We say that $x \sim^* y$ if and only if $x \sim y$ in the dual of $M$. It is trivial to check that $\sim$ (and hence also $\sim^*$) defines an equivalence relation on the ground set of $M$.
Now let $G$ satisfy the hypothesis of Gallai's Lemma and let $M(G)$ be the matching matroid of $G$. By hypothesis, $M(G)$ does not contain any co-loops. Furthermore, if $x$ and $y$ are adjacent vertices we clearly have $x \sim^* y$. But since $G$ is connected, this implies that $V(G)$ consists of a single $\sim^*$ equivalence class. Thus, def$(G)$=1, as required.
|
|
|
|
|
4
|
|
edited Feb 23 2010 at 0:25 |
I'd say the Tutte-Berge formulaFormula, which is a wonderful result that tells you (almost) everything you want to know about matchings in graphs. Although there are many proofs of this theorem, there is a beautiful 'proof for free' using matroids. Strictly speaking, there is a proof for free of Gallai's Lemma (from which Tutte-Berge follows easily). Gallai's Lemma. Let $G$ be a connected graph such that def$(G-x)=$def$(G)$, using for all $x \in V(G)$. Then $|V(G)|$ is odd and def(G)=1. Remark: def$(G)$ denotes the number of vertices of $G$ not covered by a maximum matchingmatroid.It all magically boils down to Proof for free.In any matroid $M$ define the relation $x \sim y$ to mean $r(x)=r(y)=1$ and $r({x,y})=1$ or if $x=y$. (trivial) fact Here, $r$ is the rank function of $M$). We say that $x \sim^* y$ if and only if $x \sim y$ in any matroid, parallel elements give the dual of $M$. It is trivial to check that $\sim$ (and hence also $\sim^*$) defines an equivalence relation on the ground set of $M$. Now let $G$ satisfy the hypothesis of Gallai's Lemma and let $M(G)$ be the matching matroid of $G$. By hypothesis, $M(G)$ does not contain any co-loops. Furthermore, if $x$ and $y$ are adjacent vertices we clearly have $x \sim^* y$. But since $G$ is connected, this implies that $V(G)$ consists of a single $\sim^*$ equivalence class. Thus, def$(G)$=1, as required.
|
|
|
|
|
3
|
|
edited Feb 21 2010 at 4:26 |
I'd say the Tutte-Berge formula, which is a wonderful result that tells you (almost) everything you want to know about matchings in graphs. Although there are many proofs of this theorem, there is a beautiful 'proof for free' using matroids. Strictly speaking, there is a proof for free of Gallai's Lemma (from which Tutte-Berge follows easily), using the matching matroid. It all magically boils down to the (trivial) fact that in any matroid, parallel elements give an equivalence relation on the ground set.
|
|
|
|
|
2
|
|
edited Feb 21 2010 at 1:38 |
I'd say the Tutte-Berge formula, which is a wonderful result that tells you (almost) everything you want to know about matchings in graphs. Although there are many proofs of this theorem, there is a beautiful 'proof for free' using matroids. Strictly speaking, there is a proof for free of Gallai's Lemma (from which Tutte-Berge follows easily), using the matching matroid. It all magically boils down to the (trivial) fact that in any matroid, parallel elements give an equivalence relation on the ground set.
|
|
|
|
|
1
|
|
answered Feb 21 2010 at 0:57 |
I'd say the Tutte-Berge formula, which is a wonderful result that tells you (almost) everything you want to know about matchings in graphs. Although there are many proofs of this theorem, there is a beautiful 'proof for free' using matroids. Strictly speaking, there is a proof for free of Gallai's Lemma (from which Tutte-Berge follows easily), using the matching matroid. It all magically boils down to the (trivial) fact that in any matroid, parallel elements give an equivalence relation on the ground set.
|
|
|
