Let $\mathcal{G}\_{<\omega}$ be the set of graphs $G = (V,E)$ such that $V = \{0,\ldots,n\}$ for some $n \geq 0$ and $E \subseteq \mathcal{P}\_2(V) = \{\{a,b\} : a,b \in V \textrm{ and } a\neq b\}$. We write $\mathcal{G}\_{<\omega}/\cong$ for the set of isomorphism classes. The following defines an ordering relation on $\mathcal{G}\_{<\omega}/\cong$:



> 
> 
> > 
> > $[G]\_\cong \leq [H]\_\cong$ if and only if there is a collection $\mathcal{S}$ of non-empty, connected and pairwise disjoint subsets of $H$ and a bijection $\varphi: G\to \mathcal{S}$ such that whenever $\{v,w\}\in E(G)$ there are $x\in\varphi(v), y\in\varphi(w)$ such that $\{x,y\} \in E(H)$.
> > 
> > 
> > 
> 
> 
> 


In other words, this is the "minor ordering".


Questions:


1) Is $(\mathcal{G}\_{<\omega}/\cong, \leq)$ a lattice?


2) If $P$ is a finite poset, is there an order-embedding $e: P\to \mathcal{G}\_{<\omega}/\cong$?



Minor ordering for finite graphs
Re part (1): It's certainly not a lattice. For instance if $G$ is a four-vertex path and $H=K\_{1,3}$, a four-vertex star, then the minimal graphs that contain both $G$ and $H$ as minors are a four-vertex graph with a triangle and a tail, or a five-vertex tree. Neither is a minor of the other: the five-vertex tree has too many vertices to be a minor of the four-vertex triangle-and-tail, and in the other direction taking a minor of a five-vertex tree can't produce anything with a cycle. So $G$ and $H$ have no unique least upper bound.


By the way, the way you define minors forces the graphs to be simple. This works, but the theory is often a little simpler (e.g. forbidden minors are smaller) if you allow multiple adjacencies and self-loops instead.


