4
$\begingroup$

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,
Doesbaddel

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Matthew Leingang Aug 25 '18 at 14:31
  • 1
    $\begingroup$ 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$.” $\endgroup$ – Matthew Leingang Aug 25 '18 at 14:33
  • $\begingroup$ 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. $\endgroup$ – Doesbaddel Aug 25 '18 at 14:35
  • 1
    $\begingroup$ 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$. $\endgroup$ – Berci Aug 25 '18 at 14:39
  • 1
    $\begingroup$ 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? $\endgroup$ – Henning Makholm Aug 25 '18 at 15:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.