Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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 1

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

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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