Relations and a graph

Question

enter image description here

1. Find at least one binary relation R on the set M of vertices of some subgraph of the graph ​ such that the ordered pair (c, d) belongs to this subgraph. (Define the relation R by defining it for all individual pairs of elements.)
2. How many total (linear) orders defined on the set of vertices of some subgraph of the graph ​ can be found? Consider all subgraphs.
3. Is it possible to find a subgraph of the given graph ​, such that this subgraph is a graphic representation of an equivalence relation on the set of its vertices? Give reasoning.

Answer 1

Is a subgraph a proper subgraph? In the usual definition, a graph $G$ is a subgraph of $G$.

---

1. Consider the subgraph with vertices $\{c, d\}$.

2. Consider

   • which of the single vertex subgraphs define a total order;
   • which of the double vertex subgraphs define a total order;
   • which of the triple vertex subgraphs define a total order (add each external vertex to each of the above);
   • ...

3. Consider the loop $(a, a)$.