0
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Hans Hüttel Apr 8 '17 at 19:03
0
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.