I'm new to graph theory, and I am studying a question about graphs generated using 4 vertices, and $V = \{a, b, c, d\}$, and let E be a symmetric relation on V.
So at this moment, I have successfully managed to draw all 11 non-isomorphic graphs using the vertices given, and I have a rough idea about the symmetric relation given, so it's like $E = \{(a, b), (b, a)\}$ would be a valid example to the symmetric relation (P.S. Correct me if I am wrong, I am actually not sure about my understanding here)
The question asks further about selecting all graphs whose relation E is transitive after adding in all the loops.
I don't understand two things here:
- How does the transitive relation defined on graph influence the looking of a graph? In other words, what's the visualization of a graph that has this transitive property of edges on it?
- What happens to the initial 11 graphs if we are allowing loops in the graphs now?
Thanks for helping.
For a relation $\sim$ to be transitive means $x \sim y, y\sim z \Rightarrow x \sim z$. For a symmetric relation this implies that for $x\sim y$ also $x\sim x$ and $y\sim y$ hold. Drawing the graph this would be loops, so if we want to speak about a graph being a transitive symmetric relation, we need to impose loops on all vertices, which are incident to an edge.
That being said, note that a connected graph defines a transitive relation, if and only if it is a complete graph (edges between any two distinct vertices). This is because transitivity implies that whenever there are two consecutive edges the endpoints are connected by an edge. So any path can be iteratively made shorter until it becomes an edge from start to endpoint.
Hence in general every graph, which defines a transitive relation, is given by a disjoint union of complete graphs.