Another nice one. I liked this one enough for a strong upvote. Here is my solution:
Say the graph is G=G0. If G has no vertices of infinite degree then it has a countably infinite edgeless subgraph: we just pick any vertex, throw away its neighbors, pick another vertex, throw away its neighbors, etc. Since we can always do this, we end up picking countably infinite vertices without any edges between them, so we’re done.
Now suppose G has at least one vertex of infinite degree, say v1. Let G1 be the subgraph consisting of the neighbors of v1 and all the edges between them. If this subgraph has no vertices of infinite degree then we’re again done as above, and if there is such a vertex v2 then we look at the subgraph of all of its neighbors in G1, say G2. If we can continue this process indefinitely then we end up picking countably infinitely many vertices vi which form a complete subgraph, and if it stops then one of the Gi and thus G itself has a countably infinite edgeless subgraph.
Another nice one. I liked this one enough for a strong upvote. Here is my solution:
Say the graph is G=G0. If G has no vertices of infinite degree then it has a countably infinite edgeless subgraph: we just pick any vertex, throw away its neighbors, pick another vertex, throw away its neighbors, etc. Since we can always do this, we end up picking countably infinite vertices without any edges between them, so we’re done.
Now suppose G has at least one vertex of infinite degree, say v1. Let G1 be the subgraph consisting of the neighbors of v1 and all the edges between them. If this subgraph has no vertices of infinite degree then we’re again done as above, and if there is such a vertex v2 then we look at the subgraph of all of its neighbors in G1, say G2. If we can continue this process indefinitely then we end up picking countably infinitely many vertices vi which form a complete subgraph, and if it stops then one of the Gi and thus G itself has a countably infinite edgeless subgraph.