Let G be an infinite graph such that for any countably infinite vertex set A there is a vertex p, not in A, joined to infinitely many elements of A. Show that G has a countably infinite vertex set A such that G contains uncountably infinitely many vertices p joined to infinitely many elements of A. P. Erdos, A. Hajnal graph theorycombinatorics proposedcombinatorics