# Prove, that relation $R(G,\preccurlyeq_G) \; (G_1 \preccurlyeq_G G_2: G_1 \text{ is subgraph of } G_2)$ is a Poset

I'm currently studying for my exams and want to know if my proof of the following task is done correctly:

Prove, that the relation $R(G,\preccurlyeq_G) \; (G_1 \preccurlyeq_G G_2 \Leftrightarrow G_1 \text{is a subgraph of } G_2)$ of two graphs (unsigned, labeled) is a partial ordered set (Poset).

Poset$\implies$ Relation must be reflexive, antisymmetric and transitive.

Reflexive:

Let $G=(V,E): V=\text{Vertices},\quad E= \text{Edges}$

$(G_1,G_1)\Longleftrightarrow \text{Every graph is a subgraph of itself.}$
That means, that $(G_1\preccurlyeq_G G_1)\Longleftrightarrow V_1$ is a subset of $V_2$ and $E_1$ is a subset of $E_2$

Antisymmetric:

$(G_1 \preccurlyeq_G G_2)$ and $(G_2 \preccurlyeq_G G_1) \implies G_1 = G_2$
$\Longleftrightarrow (V_1$ is a subset of $V_2$ and $E_1$ is a subset of $E_2)$ and $(V_2$ is a subset of $V_1$ and $E_2$ is a subset of $E_1)\implies G_1=G_2 \text{ because }V_1$ is a subset of $V_2$ and $V_2$ is a subset of $V_1 \implies V_1 = V_2$ (Analogous to $E$)

Transitive:

$(G_1 \preccurlyeq_G G_2)$ and $(G_2 \preccurlyeq_G G_3) \implies (G_1 \preccurlyeq_G G_3)$
$\Longleftrightarrow (V_1$ is a subset of $V_2$ and $E_1$ is a subset of $E_2)$and$(V_2$ is a subset of $V_3$ and $E_2$ is a subset of $E_3) \implies (V_1$ is a subset of $V_3$ and $E_1$ is a subset of $E_3)$

If $V_1$ is a subset of $V_2$ and $E_1$ is a subset of $E_2$ would be the same as: $|V_1| \leq |V_2|$ and $|E_1| \leq |E_2|$
Because $V_2$ is a subset of $V_3$ and $E_2$ is a subset of $E_3$ would be the same as: $|V_2| \leq |V_3|$ and $|E_2| \leq |E_3|$ is
$V_1$ is a subset of $V_3$ and $E_1$ is a subset of $E_3 \Longleftrightarrow |V_1| \leq |V_3|$ and $|E_1| \leq |E_3|$
and that's why $(G_1 \preccurlyeq_G G_3).$

$\implies R(G,\preccurlyeq_G)$ is a $\textit{Poset}$

Kind regards,
• Hi, welcome. Logically, your proof looks sound. Notationally, it's a little dense. I would suggest writing out your sentences in English. Replace $\wedge$ with “and”, etc. Also, $\sim$ is a weird choice of symbol for a partial ordering. I've seen it more often used for equivalence relation. But that's not your choice, I know. – Matthew Leingang Aug 25 '18 at 14:31
• For instance, “$(G_1 \sim G_2)\in R \wedge (G_2 \sim G_3)\in R \implies (G_1 \sim G_3) \in R$” can simply be written as “Suppose $G_1 \sim G_2$ and $G_2 \sim G_3$. We wish to show that $G_1 \sim G_3$.” – Matthew Leingang Aug 25 '18 at 14:33
• Thank you! Alright, I will try to do that. Yeah you're right. We actually used this symbol: $(\preccurlyeq_G); \;R(G, \preccurlyeq_G)$, but I was too lazy to type it out everytime/copy-paste it. Thank you for your answer. – Doesbaddel Aug 25 '18 at 14:35
• The notation '$(G_1\sim G_2)\in R$' seems superfluous. Either use $\sim$ or $R$ for the relation, e.g. saying that the pair $(G_1,G_2)\,\in R$ abbreviated as $G_1\,R\,G_2$, or use $G_1\sim G_2$. – Berci Aug 25 '18 at 14:39
• I don't think the relation you have written is a set in the first place, unless you have an invisible assumption that vertex names are drawn from some particular known set. What does $G$ in $(G,\preccurlyeq_G)$ mean? – Henning Makholm Aug 25 '18 at 15:06