3 ms·
Surely not _any_ property? From the article I understood that it’s only those that are monotonic under adding edges?
by layer8 5y ago
Surely not _any_ property? From the article I understood that it’s only those that are monotonic under adding edges?
- nawgz 5y agoIt seems to me most graph problems that people care about are monotonic under adding edges. Actually, I can't think of a single problem in graph theory I've done where that wouldn't hold.
- cevi 5y agoBeing a https://en.wikipedia.org/wiki/Perfect_graph https://en.wikipedia.org/wiki/Perfect_graph is not monotonic under adding edges, and it's certainly an interesting property for a graph to have! (But yes, most interesting properties are monotonic under adding edges)
- deleted 5y ago[deleted]
- thaumasiotes 5y ago> It seems to me most graph problems that people care about are monotonic under adding edges. Actually, I can't think of a single problem in graph theory I've done where that wouldn't hold. https://en.wikipedia.org/wiki/Braess%27s_paradox https://en.wikipedia.org/wiki/Braess%27s_paradox is very famous.
- darig 5y ago
- thomasahle 5y agoYou are right! Luckily that's the definition of a graph property . Something that definitely won't work: The parity of the number of edges. Still, it's pretty general.