Let $K$ be an infinite cardinal. Then, by the Robertson–Seymour theorem, the set of graphs with fewer than $K$ vertices and edges form a well-quasi-order.

In terms of $K$, what is the maximal order type of this well-quasi-order?

(The maximal order type of a well-quasi-order $(X,\le_X$) is the supremum of the ordinals that embed into $\le_X$.)

false premise: the second sentence in the OP is false: by [Robin Thomas,A counter-example to 'Wagner' conjecture' for infinite graphs, Math. Proc. Camb. Phil. Soc. (1988),103, 55-57], if $K=2^{\aleph_0}$, then your set of graphs $G$ with at most $K$ vertices isnota well-quasi-order. The question will have to be corrected. I don't know how though. An obvious idea would be to impose an upper bound on $K$, but making it $K<2^{\aleph_0}$ would be rather uninformative, for reasons related to forcing and the unnknown size of the cardinality of the continuum. $\endgroup$ – Peter Heinig Feb 22 '18 at 11:27necessarilyhas at most $K$ edges. $\endgroup$ – Peter Heinig Feb 22 '18 at 13:28