# An edge that connects 3 vertices

Are there any practical situations that can be represented using a modified definition of an edge - where each edge connects three vertices instead of two?

-
Sure, for example the notion of three points being collinear. See en.wikipedia.org/wiki/Hypergraph . –  Qiaochu Yuan Aug 12 '12 at 17:26
Would a triangle do? It sort of connects 3 vertices. Another possibility: in a directed graph one has two functions $s,t: E \to V$ called source and target. So one could up this to three functions! Then any selection of 2 of these would define a directed graph. –  Ronnie Brown Aug 13 '12 at 9:09
The relevant term is "hypergraph", which have a large literature. Edges in a hypergraph may be an arbitrary subset of the vertex set. –  Chris Godsil Aug 19 '12 at 13:03

## 1 Answer

You're talking about $3$-uniform hypergraphs. They will arise in a range of contexts, some of which are:

• Steiner triple systems are $3$-uniform hypergraphs in which each pair of vertices belongs to exactly one hyperedge.

• Triangulations of surfaces (e.g. the plane).

• The problem of completing a partial triangulation of the complete tripartite graph $K_{n,n,n}$ has been shown to be NP-complete. Charlie Colbourn gave a polynomial time reduction of this problem to the problem of completing partial Latin squares, thereby showing that this problem is also NP-complete (ref.).

These contexts are more areas of pure mathematics, and can be rephrased to not be $3$-uniform hypergraphs (however, I'm guessing all $3$-uniform hypergraph problems can be thus rephrased).

Combinatorial designs, such as Steiner triple systems, have applications in software testing. Hypergraphs in general arise in the study of complex networks, but I haven't seen the particular case of $3$-uniform hypergraphs arise.

However, we don't need applications for mathematics to be interesting; the following quote applies to mathematics as well as physics.

Physics is like sex. Sure you can get some interesting results, but that's not why we do it. -- Richard Feynman (disputed).

-