Skip to main content
added 72 characters in body
Source Link
Dima Pasechnik
  • 14k
  • 2
  • 34
  • 70

Assume $G$ connected (thanks to Richard Stanley for pointing this out). The only possibility is that $G$ is a complete graph. Indeed, if $G$ has a path $abc$ of length 2, so that there is no edge between $a$ and $c$, then one can see that the augmentation property for independent (in the sense of matroid) sets with vertices in $abc$ will be violated. Take the independent sets $\{a,c\}$ and $\{b\}$. Then by the augmentation property there should be an element in the bigger independent set that one can add to the smaller one, and still have an independent set. But this is not possible, as $b$ is connected by edges to both $a$ and $c$. QED

The only possibility is that $G$ is a complete graph. Indeed, if $G$ has a path $abc$ of length 2, so that there is no edge between $a$ and $c$, then one can see that the augmentation property for independent (in the sense of matroid) sets with vertices in $abc$ will be violated. Take the independent sets $\{a,c\}$ and $\{b\}$. Then by the augmentation property there should be an element in the bigger independent set that one can add to the smaller one, and still have an independent set. But this is not possible, as $b$ is connected by edges to both $a$ and $c$. QED

Assume $G$ connected (thanks to Richard Stanley for pointing this out). The only possibility is that $G$ is a complete graph. Indeed, if $G$ has a path $abc$ of length 2, so that there is no edge between $a$ and $c$, then one can see that the augmentation property for independent (in the sense of matroid) sets with vertices in $abc$ will be violated. Take the independent sets $\{a,c\}$ and $\{b\}$. Then by the augmentation property there should be an element in the bigger independent set that one can add to the smaller one, and still have an independent set. But this is not possible, as $b$ is connected by edges to both $a$ and $c$. QED

Source Link
Dima Pasechnik
  • 14k
  • 2
  • 34
  • 70

The only possibility is that $G$ is a complete graph. Indeed, if $G$ has a path $abc$ of length 2, so that there is no edge between $a$ and $c$, then one can see that the augmentation property for independent (in the sense of matroid) sets with vertices in $abc$ will be violated. Take the independent sets $\{a,c\}$ and $\{b\}$. Then by the augmentation property there should be an element in the bigger independent set that one can add to the smaller one, and still have an independent set. But this is not possible, as $b$ is connected by edges to both $a$ and $c$. QED