Let $G=(V,E)$ be a simple graph which has the following property. If $(u,v)\in E$ and $(v,s)\in E$ then $(u,s)\in E$. What kind of graph is this? Does it have any name and special property?

  • $\begingroup$ Per @bof, you may want to change the hypotheses so as to stop all such graphs being merely collections of disconnected points. $\endgroup$ – Patrick Stevens Feb 9 '18 at 9:09
  • $\begingroup$ FYI, strictly speaking, to write '$(u,v)\in E$' is wrong, at least according to what is currently the usual formalisation of 'graph' via set theory (see e.g. Diestel: Graph Theory); in that formalism, a simple graph has two-sets as edges, and $(u,v)$ in set-theory is not equal to the two-set containing only $u$ and $v$. (Of course, $(u,v)$ in the usual formalisation is a two-set, but another one: $(u,v)=\{u,\{u,v\}\}$. $\endgroup$ – Peter Heinig Feb 9 '18 at 18:32

Such a graph is a disjoint union of complete graphs. Indeed, it's easy to prove by induction on the number of vertices of any connected subgraph that any connected subgraph is complete.

  • $\begingroup$ A simple group with the stated property is an empty graph, a graph with no edges. Because, if $(u,v)\in E,$ then $(v,u)\in E$ and $(u,u)\in E,$ so the graph is not simple. $\endgroup$ – bof Feb 9 '18 at 8:24
  • $\begingroup$ @bof True. My statement is still correct though ;) $\endgroup$ – Patrick Stevens Feb 9 '18 at 9:08

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.