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.
Biject the graph to z, drop all odd edges and you get a countably infinite subgraph. The key point is that you’re looking for any subgraph that is complete or edgeless.
Show that every countably infinite graph contains either a countably infinite complete subgraph, or 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.
This sounds obviously false to me? Why can’t you have a countably infinite graph where all vertices have degree 2?
Biject the graph to z, drop all odd edges and you get a countably infinite subgraph. The key point is that you’re looking for any subgraph that is complete or edgeless.
Ah! I see.