0

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.
Klara11
  • 3
  • This looks a lot like a homework problem, and you should do your own homework. Please tell us what you have done to solve it yourself. – Hans Hüttel Apr 08 '17 at 19:03

1 Answers1

0

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)$.

Thumbnail
  • 563