Title needs improvement
-
In Build one, problem. regarding connected graph, it is sometimes good to consider [complementary graph
If a graph G with 3 or more vertices is disconnected, then for any vertex a, there is some disconnected vertex b (since if there is not, it contradicts that the graph is disconnected). At this time, for any vertex c, which is neither a nor b, there can be no edge of both ac and bc in G (since if there were, a and b would be connected via c). Given a complementary graph H, edge ab is contained in H and either ac or bc is contained in H, so abc is connected
This page is auto-translated from /nishio/連結なグラフの補グラフ using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.