Sets (Proofs)

Question

Let V be a set, and let E be a symmetric relation on V.  We call any such pairing G = (V, E) a graph, and call the elements of V the vertices, and the elements of E the edges.

By convention,

•We don’t allow an edge to start and end at the same vertex (these would be called “loops”).

•We  visually  represent  an  edge  as  a  single  curve  connecting  two  vertices  (instead  of  using  two  directedarrows).

We say that two graphs are “isomorphic” if you can get one from the other by relabeling the points.  For example, on the vertex set {1,2,3} the edge relations E1={(1,2),(2,1),(3,2),(2,3)} and E2={(1,3),(3,1),(2,3),(3,2)}. In other words, two graphs are “the same” if they “look the same” when you ignore the labels on the vertices.

(1)  There are 4 possible graphs on the vertices {1,2,3}.  Find them.  (You do not need to prove your result.)

(2)  Find all possible graphs on the vertices {1,2,3,4}. Identify all such graphs whose relation E is transitive. (You  do  not  need  to  prove  your  result.   Note:  If  you  add  in  the  loops  you  will  have  found  all  types  of equivalence relations on {1,2,3,4}.)

Answer 1

 

Symmetry in equivalence relationship is a→b, b→a.

(1) The only way I can interpret this question is by interchanging vertices:

E1={(1,2),(2,1),(3,2),(2,3)}

E2={(1,3),(3,1),(2,3),(3,2)} [vertices 2 and 3 in E1 change places]

E3={(2,3),(3,2),(1,3),(3,1)} [vertices 1 and 2 in E1 change places]

E4={(3,2),(2,3),(1,2),(2,1)} [vertices 1 and 3 in E1 change places]

So G1=(V,E1), G2=(V,E2), G3=(V,E3), G4=(V,E4).

(2)

E1={(1,2),(2,1),(2,3),(3,2),(3,4),(4,3)}

E2={(3,2),(2,3),(2,1),(1,2),(1,4),(4,1)} [vertices 1 and 3 in E1 change places]

E3={(1,4),(4,1),(4,3),(3,4),(3,4),(4,3)} [vertices 2 and 4 in E1 change places]

E4={(2,1),(1,2),(1,3),(3,1),(3,4),(4,3)} [vertices 1 and 2 in E1 change places]

E5={(4,2),(2,4),(2,3),(3,2),(3,1),(1,3)} [vertices 1 and 4 in E1 change places]

E6={(1,3),(3,1),(3,2),(2,3),(2,4),(4,2)} [vertices 2 and 3 in E1 change places]

E7={(1,2),(2,1),(2,4),(4,2),(4,3),(3,4)} [vertices 3 and 4 in E1 change places]

G1=(V,E1), G2=(V,E2), G3=(V,E3), G4=(V,E4), G5=(V,E5), G6=(V,E6), G7=(V,E7).

For transitivity, a→b, b→c⇒a→c. More to follow (I hope!)...

 

Comments

I have to say I’m not confident about any of this, and I can’t find any transitivity in (2), because, as I understand it, E1 does not exhibit transitivity, and E2-E7 are structured identically to E1.