In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

field of

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, the friendship graph (or Dutch windmill graph or -fan) is a

planar Planar is an adjective meaning "relating to a plane (geometry)". Planar may also refer to: Science and technology * Planar (computer graphics), computer graphics pixel information from several bitplanes * Planar (transmission line technologies), ...

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...

with vertices and edges. The friendship graph can be constructed by joining copies of the

cycle graph In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...

with a common vertex, which becomes a

universal vertex In graph theory, a universal vertex is a vertex of an undirected graph that is adjacent to all other vertices of the graph. It may also be called a dominating vertex, as it forms a one-element dominating set in the graph. (It is not to be confused ...

for the graph. By construction, the friendship graph is isomorphic to the

windmill graph In the mathematical field of graph theory, the windmill graph is an undirected graph constructed for and by joining copies of the complete graph at a shared universal vertex. That is, it is a 1-clique-sum of these complete graphs. Propert ...

. It is unit distance with girth 3, diameter 2 and radius 1. The graph is isomorphic to the

butterfly graph In the mathematical field of graph theory, the butterfly graph (also called the bowtie graph and the hourglass graph) is a planar, undirected graph with 5 vertices and 6 edges. It can be constructed by joining 2 copies of the cycle graph with a ...

Friendship theorem

The friendship theorem of states that the finite graphs with the property that every two vertices have exactly one neighbor in common are exactly the friendship graphs. Informally, if a group of people has the property that every pair of people has exactly one friend in common, then there must be one person who is a friend to all the others. However, for infinite graphs, there can be many different graphs with the same cardinality that have this property. A combinatorial proof of the friendship theorem was given by Mertzios and Unger. Another proof was given by Craig Huneke. A formalised proof in

Metamath Metamath is a formal language and an associated computer program (a proof checker) for archiving, verifying, and studying mathematical proofs. Several databases of proved theorems have been developed using Metamath covering standard results in ...

was reported by Alexander van der Vekens in October 2018 on the Metamath mailing list.

Labeling and colouring

The friendship graph has

chromatic number In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices ...

3 and

chromatic index In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blu ...

. Its

chromatic polynomial The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to s ...

can be deduced from the chromatic polynomial of the cycle graph and is equal to :

(x-2)^n (x-1)^n x

. The friendship graph is edge-graceful if and only if is odd. It is graceful if and only if or . Every friendship graph is factor-critical.

Extremal graph theory

According to

extremal graph theory Extremal graph theory is a branch of combinatorics, itself an area of mathematics, that lies at the intersection of extremal combinatorics and graph theory. In essence, extremal graph theory studies how global properties of a graph influence local ...

, every graph with sufficiently many edges (relative to its number of vertices) must contain a

k

-fan as a subgraph. More specifically, this is true for an

n

-vertex graph if the number of edges is :

\left\lfloor \frac\right\rfloor + f(k),

where

f(k)

k^2-k

k

is odd, and

f(k)

k^2-3k/2

k

is even. These bounds generalize

Turán's theorem In graph theory, Turán's theorem bounds the number of edges that can be included in an undirected graph that does not have a complete subgraph of a given size. It is one of the central results of extremal graph theory, an area studying the large ...

on the number of edges in a

triangle-free graph In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with g ...

, and they are the best possible bounds for this problem, in that for any smaller number of edges there exist graphs that do not contain a

k

-fan..

References

{{reflist Parametric families of graphs Planar graphs