Complete graph

From Wikipedia for FEVERv2
Jump to navigation Jump to search

Complete graph_table_infobox_0

Complete graphComplete graph_header_cell_0_0_0
VerticesComplete graph_header_cell_0_1_0 nComplete graph_cell_0_1_1
EdgesComplete graph_header_cell_0_2_0 n

( n − 1 )

2



{\displaystyle \textstyle {\frac {n(n-1)}{2}}}Complete graph_cell_0_2_1

RadiusComplete graph_header_cell_0_3_0 {



0


n ≤ 1



1


otherwise





{\displaystyle \left\{{\begin{array}{ll}0&n\leq 1\\1&{\text{otherwise}}\end{array}}\right.}Complete graph_cell_0_3_1

DiameterComplete graph_header_cell_0_4_0 {



0


n ≤ 1



1


otherwise





{\displaystyle \left\{{\begin{array}{ll}0&n\leq 1\\1&{\text{otherwise}}\end{array}}\right.}Complete graph_cell_0_4_1

GirthComplete graph_header_cell_0_5_0 {




n ≤ 2



3


otherwise





{\displaystyle \left\{{\begin{array}{ll}\infty &n\leq 2\\3&{\text{otherwise}}\end{array}}\right.}Complete graph_cell_0_5_1

AutomorphismsComplete graph_header_cell_0_6_0 n! (Sn)Complete graph_cell_0_6_1
Chromatic numberComplete graph_header_cell_0_7_0 nComplete graph_cell_0_7_1
Chromatic indexComplete graph_header_cell_0_8_0 Complete graph_cell_0_8_1
SpectrumComplete graph_header_cell_0_9_0 {




n = 0



{

0

1


}


n = 1



{

( n − 1

)

1


, −

1

n − 1


}



otherwise





{\displaystyle \left\{{\begin{array}{lll}\emptyset &n=0\\\left\{0^{1}\right\}&n=1\\\left\{(n-1)^{1},-1^{n-1}\right\}&{\text{otherwise}}\end{array}}\right.}Complete graph_cell_0_9_1

PropertiesComplete graph_header_cell_0_10_0 Complete graph_cell_0_10_1
NotationComplete graph_header_cell_0_11_0 KnComplete graph_cell_0_11_1

In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. Complete graph_sentence_0

A complete digraph is a directed graph in which every pair of distinct vertices is connected by a pair of unique edges (one in each direction). Complete graph_sentence_1

Graph theory itself is typically dated as beginning with Leonhard Euler's 1736 work on the Seven Bridges of Königsberg. Complete graph_sentence_2

However, drawings of complete graphs, with their vertices placed on the points of a regular polygon, appeared already in the 13th century, in the work of Ramon Llull. Complete graph_sentence_3

Such a drawing is sometimes referred to as a mystic rose. Complete graph_sentence_4

Properties Complete graph_section_0

The complete graph on n vertices is denoted by Kn. Complete graph_sentence_5

Some sources claim that the letter K in this notation stands for the German word komplett, but the German name for a complete graph, vollständiger Graph, does not contain the letter K, and other sources state that the notation honors the contributions of Kazimierz Kuratowski to graph theory. Complete graph_sentence_6

Kn has n(n − 1)/2 edges (a triangular number), and is a regular graph of degree n − 1. Complete graph_sentence_7

All complete graphs are their own maximal cliques. Complete graph_sentence_8

They are maximally connected as the only vertex cut which disconnects the graph is the complete set of vertices. Complete graph_sentence_9

The complement graph of a complete graph is an empty graph. Complete graph_sentence_10

If the edges of a complete graph are each given an orientation, the resulting directed graph is called a tournament. Complete graph_sentence_11

Kn can be decomposed into n trees Ti such that Ti has i vertices. Complete graph_sentence_12

Ringel's conjecture asks if the complete graph K2n+1 can be decomposed into copies of any tree with n edges. Complete graph_sentence_13

This is known to be true for sufficiently large n. Complete graph_sentence_14

The number of matchings of the complete graphs are given by the telephone numbers Complete graph_sentence_15

Complete graph_description_list_0

  • 1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, ... (sequence in the OEIS).Complete graph_item_0_0

These numbers give the largest possible value of the Hosoya index for an n-vertex graph. Complete graph_sentence_16

The number of perfect matchings of the complete graph Kn (with n even) is given by the double factorial (n − 1)! Complete graph_sentence_17

!. Complete graph_sentence_18

The crossing numbers up to K27 are known, with K28 requiring either 7233 or 7234 crossings. Complete graph_sentence_19

Further values are collected by the Rectilinear Crossing Number project. Complete graph_sentence_20

Rectilinear Crossing numbers for Kn are Complete graph_sentence_21

Complete graph_description_list_1

  • 0, 0, 0, 0, 1, 3, 9, 19, 36, 62, 102, 153, 229, 324, 447, 603, 798, 1029, 1318, 1657, 2055, 2528, 3077, 3699, 4430, 5250, 6180, ... (sequence in the OEIS).Complete graph_item_1_1

Geometry and topology Complete graph_section_1

A complete graph with n nodes represents the edges of an (n − 1)-simplex. Complete graph_sentence_22

Geometrically K3 forms the edge set of a triangle, K4 a tetrahedron, etc. Complete graph_sentence_23

The Császár polyhedron, a nonconvex polyhedron with the topology of a torus, has the complete graph K7 as its skeleton. Complete graph_sentence_24

Every neighborly polytope in four or more dimensions also has a complete skeleton. Complete graph_sentence_25

K1 through K4 are all planar graphs. Complete graph_sentence_26

However, every planar drawing of a complete graph with five or more vertices must contain a crossing, and the nonplanar complete graph K5 plays a key role in the characterizations of planar graphs: by Kuratowski's theorem, a graph is planar if and only if it contains neither K5 nor the complete bipartite graph K3,3 as a subdivision, and by Wagner's theorem the same result holds for graph minors in place of subdivisions. Complete graph_sentence_27

As part of the Petersen family, K6 plays a similar role as one of the forbidden minors for linkless embedding. Complete graph_sentence_28

In other words, and as Conway and Gordon proved, every embedding of K6 into three-dimensional space is intrinsically linked, with at least one pair of linked triangles. Complete graph_sentence_29

Conway and Gordon also showed that any three-dimensional embedding of K7 contains a Hamiltonian cycle that is embedded in space as a nontrivial knot. Complete graph_sentence_30

Examples Complete graph_section_2

Complete graphs on n vertices, for n between 1 and 12, are shown below along with the numbers of edges: Complete graph_sentence_31

Complete graph_table_general_1

K1: 0Complete graph_header_cell_1_0_0 K2: 1Complete graph_header_cell_1_0_1 K3: 3Complete graph_header_cell_1_0_2 K4: 6Complete graph_header_cell_1_0_3
Complete graph_cell_1_1_0 Complete graph_cell_1_1_1 Complete graph_cell_1_1_2 Complete graph_cell_1_1_3
K5: 10Complete graph_header_cell_1_2_0 K6: 15Complete graph_header_cell_1_2_1 K7: 21Complete graph_header_cell_1_2_2 K8: 28Complete graph_header_cell_1_2_3
Complete graph_cell_1_3_0 Complete graph_cell_1_3_1 Complete graph_cell_1_3_2 Complete graph_cell_1_3_3
K9: 36Complete graph_header_cell_1_4_0 K10: 45Complete graph_header_cell_1_4_1 K11: 55Complete graph_header_cell_1_4_2 K12: 66Complete graph_header_cell_1_4_3
Complete graph_cell_1_5_0 Complete graph_cell_1_5_1 Complete graph_cell_1_5_2 Complete graph_cell_1_5_3

See also Complete graph_section_3

Complete graph_unordered_list_2


Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Complete graph.