Hubbry Logo
Complete graphComplete graphMain
Open search
Complete graph
Community hub
Complete graph
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Complete graph
Complete graph
Complete graph
View on Wikipedia
from Wikipedia
Complete graph
K7, a complete graph with 7 vertices
Verticesn
Edges
Radius
Diameter
Girth
Automorphismsn! (Sn)
Chromatic numbern
Chromatic index
  • n if n is odd
  • n − 1 if n is even
Spectrum
Properties
NotationKn
Table of graphs and parameters

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. 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).[1]

Graph theory itself is typically dated as beginning with Leonhard Euler's 1736 work on the Seven Bridges of Königsberg. However, drawings of complete graphs, with their vertices placed on the points of a regular polygon, had already appeared in the 13th century, in the work of Ramon Llull.[2] Such a drawing is sometimes referred to as a mystic rose.[3]

Properties

[edit]

The complete graph on n vertices is denoted by Kn. Some sources claim that the letter K in this notation stands for the German word komplett,[4] 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.[5]

Kn has n(n − 1)/2 edges (a triangular number), and is a regular graph of degree n − 1. All complete graphs are their own maximal cliques. They are maximally connected as the only vertex cut which disconnects the graph is the complete set of vertices. The complement graph of a complete graph is an empty graph.

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

Kn can be decomposed into n trees Ti such that Ti has i vertices.[6] Ringel's conjecture asks if the complete graph K2n+1 can be decomposed into copies of any tree with n edges.[7] This is known to be true for sufficiently large n.[8][9]

The number of all distinct paths between a specific pair of vertices in Kn+2 is given[10] by

where e refers to Euler's constant, and

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

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

These numbers give the largest possible value of the Hosoya index for an n-vertex graph.[11] The number of perfect matchings of the complete graph Kn (with n even) is given by the double factorial (n − 1)!!.[12]

The crossing numbers up to K27 are known, with K28 requiring either 7233 or 7234 crossings. Further values are collected by the Rectilinear Crossing Number project.[13] Rectilinear Crossing numbers for Kn are

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 A014540 in the OEIS).

Geometry and topology

[edit]
Interactive Csaszar polyhedron model with vertices representing nodes. In the SVG image, move the mouse to rotate it.[14]

A complete graph with n nodes is the edge graph of an (n − 1)-dimensional simplex. Geometrically K3 forms the edge set of a triangle, K4 a tetrahedron, etc. The Császár polyhedron, a nonconvex polyhedron with the topology of a torus, has the complete graph K7 as its skeleton.[15] Every neighborly polytope in four or more dimensions also has a complete skeleton.

K1 through K4 are all planar graphs. 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. As part of the Petersen family, K6 plays a similar role as one of the forbidden minors for linkless embedding.[16] In other words, and as Conway and Gordon[17] proved, every embedding of K6 into three-dimensional space is intrinsically linked, with at least one pair of linked triangles. 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.

Examples

[edit]

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

K1: 0 K2: 1 K3: 3 K4: 6
K5: 10 K6: 15 K7: 21 K8: 28
K9: 36 K10: 45 K11: 55 K12: 66

See also

[edit]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Complete graph

View on Grokipedia
from Grokipedia
A complete graph is a simple undirected graph in which every pair of distinct vertices is connected by exactly one edge. The complete graph on n vertices is denoted by K_n, where n ≥ 1, and it represents the most connected simple graph possible on that vertex set. For n = 1, K_1 is a single isolated vertex; for n = 2, K_2 is a single edge; and for larger n, it forms a fully interconnected structure without loops or multiple edges. The number of edges in K_n is given by the binomial coefficient \binom{n}{2} = \frac{n(n-1)}{2}, which counts all possible pairs among the vertices. Every vertex in Kn has degree n-1, making the graph (n-1)-regular and highly symmetric, with the automorphism group isomorphic to the symmetric group Sn. Key properties include its chromatic number of n, requiring n colors for proper vertex coloring, and the chromatic polynomial (z)_n = z(z-1)\cdots(z-n+1). Additionally, K_n is Hamiltonian for n ≥ 3, containing a cycle that visits every vertex exactly once, and the number of spanning trees is n^{n-2} by Cayley's formula. For planarity, K_n is planar only for n ≤ 4 and nonplanar for n ≥ 5, as it contains a subdivision of K_5, violating Kuratowski's theorem. Complete graphs play a central role in as benchmarks for extremal problems, connectivity, and coloring. They form the foundation of , where the Ramsey number r(k,l) determines the smallest n such that any graph on n vertices contains a of size k or an independent set of size l, with K_n embodying the complete . In , theorems like Turán's address the maximum edges in a graph without a K_r subgraph, while Dirac's and Ore's theorems use degree conditions inspired by complete graphs to guarantee Hamiltonicity. Applications extend to network design, , and modeling fully connected systems in and .

Definition and Notation

Formal Definition

In the mathematical field of , a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. This structure ensures that the graph is maximally connected among simple graphs on the same vertex set, with no additional edges possible without violating simplicity. A simple graph, by definition, contains no loops (edges connecting a vertex to itself) and no multiple edges between the same pair of vertices, while the undirected nature means that edges lack direction and adjacency is symmetric. In this context, the complete graph embodies the strongest form of connectivity for undirected simple graphs, where the absence of self-loops and parallel edges maintains its foundational purity. The concept of a complete graph traces its early visual representation to the 13th century in the logical diagrams of , a Catalan philosopher and theologian, where such interconnected figures—known as the "mystic rose"—served mnemonic and combinatorial purposes in his Ars Magna system, predating modern by centuries.

Notation and Conventions

The standard notation for a complete graph on nn vertices is KnK_n, where nn is a positive representing the number of vertices. This symbol, introduced in foundational texts, succinctly denotes the graph where every pair of distinct vertices is connected by a unique edge. In literature, complete graphs are conventionally treated as unlabeled structures, meaning they are considered up to rather than with fixed vertex labels. All complete graphs on nn vertices are isomorphic to one another, as any between their vertex sets preserves the adjacency relations; labeled variants, where vertices are distinguished by identifiers, are used only in contexts requiring specific vertex distinctions, such as algorithmic implementations or matrix representations. The complement of KnK_n is the empty graph on nn vertices, denoted Kn‾\overline{K_n} or EnE_n, which consists of nn isolated vertices with no edges. This relation highlights the duality between complete and empty graphs, where the complement operation inverts the edge set while preserving the vertex set. The notation KnK_n serves as a fundamental building block in broader constructions, such as complete multipartite graphs.

Structural Properties

Number of Vertices and Edges

A complete graph KnK_n is defined with nn vertices, where every pair of distinct vertices is connected by exactly one undirected edge, resulting in the maximum possible number of edges for a simple graph on nn vertices. The total number of edges is given by the (n2)\binom{n}{2}, which equals n(n−1)2\frac{n(n-1)}{2}. This formula arises from the combinatorial principle that each edge corresponds to a unique of vertices chosen from the nn available, ensuring no self-loops or multiple edges. The sequence of edge counts for complete graphs KnK_n as nn increases—0 for n=1n=1, 1 for n=2n=2, 3 for n=3n=3, 6 for n=4n=4, and so on—corresponds to the triangular numbers, specifically the (n−1)(n-1)-th triangular number Tn−1=(n−1)n2T_{n-1} = \frac{(n-1)n}{2}. These values form the integer sequence A000217 in the On-Line Encyclopedia of Integer Sequences (OEIS), highlighting the close relationship between complete graphs and the summation of the first kk natural numbers for k=n−1k = n-1. For example, in K5K_5, there are 10 edges, matching T4=10T_4 = 10. In , the of KnK_n is an n×nn \times n with zeros along the (to exclude self-loops) and in all off-diagonal positions, formally expressed as A=Jn−InA = J_n - I_n, where JnJ_n is the all-ones matrix and InI_n is the . This structure directly encodes the complete connectivity: the entry Aij=1A_{ij} = 1 for i≠ji \neq j indicates an edge between vertices ii and jj.

Degrees and Regularity

In a complete graph KnK_n with nn vertices, where n≥1n \geq 1, each vertex is adjacent to every other distinct vertex, resulting in a degree of n−1n-1 for every vertex. This uniform degree across all vertices establishes KnK_n as a of degree n−1n-1. The regularity of KnK_n follows directly from its : since the graph includes all possible edges between distinct vertices, no vertex is excluded from connections to any others, ensuring identical adjacency counts for all. For the trivial case K1K_1, the single vertex has degree 0, which is consistent with 0-regularity in the degenerate sense, though typically regularity is discussed for n≥2n \geq 2. Applying the to KnK_n, the sum of all vertex degrees equals n(n−1)n(n-1), which is twice the number of edges, confirming the lemma's validity: ∑v∈Vdeg⁡(v)=2∣E∣=n(n−1)\sum_{v \in V} \deg(v) = 2|E| = n(n-1). This equality underscores the structural balance in complete graphs, where the total degree sum aligns precisely with the exhaustive edge connections.

Graph-Theoretic Properties

Connectivity and Distances

In a complete graph KnK_n with n≥2n \geq 2 vertices, the vertex connectivity is n−1n-1, meaning that the removal of fewer than n−1n-1 vertices leaves the graph connected, and this value equals the degree of each vertex. This high connectivity reflects the graph's structure, where every vertex is adjacent to all others, ensuring robust linkage. The diameter of KnK_n for n>1n > 1 is 1, as the longest shortest path between any two distinct vertices is a single edge. Similarly, the radius is also 1, since the eccentricity of every vertex—the maximum to any other vertex—is 1. These underscore the complete graph's efficiency in traversal, with no vertex more than one step away from any other. For n≥3n \geq 3, the girth of KnK_n is 3, determined by the smallest cycles, which are triangles formed by any three vertices. This minimal girth highlights the abundance of short cycles inherent in the complete structure.

Chromatic Number and Cliques

The chromatic number of the complete graph KnK_n, denoted χ(Kn)\chi(K_n), is equal to nn. This follows directly from the fact that every pair of vertices in KnK_n is adjacent, requiring a distinct color for each vertex to avoid adjacent vertices sharing the same color. As the quintessential example of a clique, KnK_n forms a complete clique on nn vertices, where the clique number ω(Kn)\omega(K_n) is nn, representing the size of the largest clique in the graph. This structure implies that the independence number α(Kn)\alpha(K_n), the size of the largest independent set, is 1, since any two vertices are adjacent and thus cannot both be included in an independent set. Complete graphs are perfect graphs, satisfying the condition that for every induced subgraph HH, the chromatic number equals the clique number, i.e., χ(H)=ω(H)\chi(H) = \omega(H). In KnK_n, every induced subgraph is itself a complete graph KmK_m for some m≤nm \leq n, where χ(Km)=ω(Km)=m\chi(K_m) = \omega(K_m) = m, ensuring the equality holds throughout.

Decompositions and Substructures

Edge Decompositions

A key aspect of edge decompositions in complete graphs involves partitioning the edge set into spanning subgraphs with specific structures, such as matchings or paths and cycles, which leverage the high connectivity and regularity of KnK_n. For the complete graph K2mK_{2m} on an even number of vertices, the edges can be decomposed into 2m−12m-1 s, known as a 1-factorization. This decomposition exists because K2mK_{2m} is (2m−1)(2m-1)-regular, and each covers all vertices exactly once, partitioning the edges completely. The construction, attributed to Walecki in the , places 2m−12m-1 vertices on a and the remaining vertex at , pairing the center to one vertex and connecting opposite points on the for each matching, then rotating the configuration. This 1-factorization relates to broader studies of resolvable balanced incomplete block designs and has applications in scheduling and network design. In contrast, for K2m+1K_{2m+1} on an odd number of vertices, the edges decompose into mm edge-disjoint Hamiltonian cycles. Each such cycle spans all 2m+12m+1 vertices, and since the graph is 2m2m-regular with each cycle contributing degree 2, exactly mm cycles cover all edges. Walecki's achieves this by fixing one vertex and arranging the others in a regular 2m2m-gon, forming a cycle through alternate vertices and the fixed point, then rotating the pattern mm times. This result, also known as Lucas' theorem, dates to the late and underpins decompositions in scheduling. Walecki's construction extends to decomposing K2mK_{2m} into mm edge-disjoint Hamiltonian paths. For even order, the odd degree 2m−12m-1 requires paths rather than cycles, with each path spanning 2m−12m-1 edges and endpoints receiving degree 1 to balance the . The method involves a similar : arrange vertices in two of mm each, connect them in a serpentine pattern for one path, and rotate or reflect to generate the remaining m−1m-1 paths. This partitions all m(2m−1)m(2m-1) edges exactly. Recent advances in edge decompositions include the 2020 proof of Ringel's conjecture by Montgomery, Pokrovskiy, and Sudakov, establishing that any with nn edges packs 2n+12n+1 edge-disjoint copies into K2n+1K_{2n+1}, providing a generalization beyond paths and cycles for sufficiently large nn.

Matchings and Coverings

In complete graphs, a matching is an edge subset with no shared vertices. The size of a maximum matching in KnK_n is ⌊n/2⌋\lfloor n/2 \rfloor, as edges can pair up vertices until at most one remains unpaired if nn is odd. When n=2mn = 2m is even, perfect matchings exist that saturate all vertices, and their number is given by the double factorial (2m−1)!!=(2m−1)(2m−3)⋯3⋅1(2m-1)!! = (2m-1)(2m-3)\cdots 3 \cdot 1, which counts the ways to pair vertices sequentially: the first vertex has 2m−12m-1 choices, the next unpaired has 2m−32m-3, and so on. This sequence is also known as the telephone numbers and appears as OEIS A000085. An edge cover in KnK_n is an edge subset incident to every vertex. By Gallai's identity, the minimum edge cover size ρ(Kn)\rho(K_n) equals n−ν(Kn)=n−⌊n/2⌋n - \nu(K_n) = n - \lfloor n/2 \rfloor, since KnK_n has no isolated vertices. For even n=2mn = 2m, this is mm, achieved by any perfect matching. For odd n=2m+1n = 2m+1, it is m+1m+1, obtained by a maximum matching of mm edges plus one additional edge to cover the unpaired vertex. A in KnK_n is a vertex subset incident to every edge. The number α(Kn)=1\alpha(K_n) = 1, as no two vertices form an independent set. By the complementary Gallai identity, the minimum τ(Kn)=n−α(Kn)=n−1\tau(K_n) = n - \alpha(K_n) = n-1, achieved by excluding any single vertex, whose incident edges are covered by the others. Excluding two or more leaves an uncovered edge between them.

Geometry and Embeddings

Planarity and Crossing Numbers

A complete graph KnK_n is planar if and only if n≤4n \leq 4, as K5K_5 is the smallest non-planar complete graph and contains no proper subdivisions beyond itself that alter this property. By Kuratowski's theorem, a graph is non-planar if it contains a subdivision of K5K_5 or K3,3K_{3,3} as a subgraph; since K5K_5 is itself one of these forbidden subgraphs, all KnK_n for n≥5n \geq 5 are non-planar for the same reason. For n>5n > 5, KnK_n embeds K5K_5 directly as an induced subgraph, reinforcing non-planarity without requiring subdivisions. The crossing number cr⁡(Kn)\operatorname{cr}(K_n), defined as the minimum number of edge crossings in any of KnK_n in the plane, is zero for n≤4n \leq 4 due to planarity. For n≥5n \geq 5, exact values are known for small nn: cr⁡(K5)=1\operatorname{cr}(K_5) = 1, achieved by four vertices in convex position with the fifth inside and edges crossing once; cr⁡(K6)=3\operatorname{cr}(K_6) = 3, obtained by adding a sixth vertex to the K5K_5 with minimal additional crossings. These values form the beginning of the sequence for cr⁡(Kn)\operatorname{cr}(K_n), cataloged as A000241 in the OEIS, with further exact determinations up to n=27n=27 as of 2024. The Zarankiewicz problem, which seeks the maximum edges in a bipartite graph avoiding complete bipartite subgraphs Ks,tK_{s,t}, connects to crossing numbers of complete graphs via upper-bound constructions for cr⁡(Kn)\operatorname{cr}(K_n). Specifically, Zarankiewicz's conjecture posits that cr⁡(Km,n)=⌊m2⌋⌊m−12⌋⌊n2⌋⌊n−12⌋\operatorname{cr}(K_{m,n}) = \left\lfloor \frac{m}{2} \right\rfloor \left\lfloor \frac{m-1}{2} \right\rfloor \left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor for complete bipartite graphs, providing a benchmark for crossings in bipartite drawings. To bound cr⁡(Kn)\operatorname{cr}(K_n), a standard construction partitions the nn vertices into two nearly equal sets of sizes ⌊n/2⌋\lfloor n/2 \rfloor and ⌈n/2⌉\lceil n/2 \rceil, drawn on two concentric circles or layers to minimize total crossings, yielding cr⁡(Kn)≤Z(n)\operatorname{cr}(K_n) \leq Z(n), where Z(n)Z(n) is the conjectured value. This yields the conjectured formula for cr⁡(Kn)\operatorname{cr}(K_n) as 14⌊n2⌋⌊n−12⌋⌊n−22⌋⌊n−32⌋\frac{1}{4} \left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor \left\lfloor \frac{n-2}{2} \right\rfloor \left\lfloor \frac{n-3}{2} \right\rfloor (Hill's conjecture, referenced by Guy), exact for n≤27n \leq 27 and asymptotically ∼164n4\sim \frac{1}{64} n^4.

Topological Properties

The complete graph KnK_n serves as the 1-skeleton of the (n−1)(n-1)-, where the vertices correspond to the simplex's vertices and the edges connect every pair, embedding the graph in (n−1)(n-1)-dimensional without crossings. This realization highlights the complete graph's role in simplicial geometry, as the higher-dimensional faces of the fill in the combinatorial structure beyond the mere edges. A notable embedding on a non-spherical surface occurs with K7K_7, whose 1-skeleton forms the Császár polyhedron, a with 7 vertices, 21 edges, and 14 triangular faces that realizes the complete graph on a without self-intersections. Discovered by Ákos Császár in 1949, this demonstrates that K7K_7 can be embedded on a surface of genus 1, providing a polyhedral model for the 's with the minimal number of vertices. In , embeddings of complete graphs exhibit intrinsic topological complexities, as established by the Conway-Gordon theorem. Specifically, every of K6K_6 in R3\mathbb{R}^3 contains a pair of disjoint cycles that form a non-trivially linked 2-component link, making K6K_6 intrinsically linked. Similarly, every of K7K_7 in R3\mathbb{R}^3 includes a knotted Hamiltonian cycle, rendering K7K_7 intrinsically knotted. These results, proved using algebraic invariants like linking numbers modulo 2, underscore the unavoidable knotting and linking in spatial realizations of small complete graphs.

Examples and Applications

Small Complete Graphs

The complete graph K1K_1 consists of a single vertex with no edges, representing the simplest possible graph and serving as the trivial case in graph theory. It has zero edges and is often denoted as the singleton graph. Visually, it appears as an isolated point. The complete graph K2K_2 comprises two vertices connected by a single edge, forming the basic building block for more complex graphs. With exactly one edge, it resembles a straight line segment between two points and is the smallest non-trivial complete graph. K3K_3, known as the triangle graph, features three vertices where each pair is joined by an edge, resulting in three edges total and forming a closed triangular . This graph is isomorphic to the C3C_3, emphasizing its cyclic structure without additional connections. The complete graph K4K_4 includes four vertices, each connected to every other, yielding six edges and embodying the tetrahedral graph, which corresponds to the skeleton of a regular . It is also isomorphic to the wheel graph W4W_4, though distinct from complete bipartite graphs like the utility graph K3,3K_{3,3}, which connects vertices across two disjoint sets without intra-set edges. Visually, K4K_4 can be drawn as a tetrahedron with vertices at the corners and edges along the faces, remaining planar unlike larger complete graphs starting from K5K_5. The number of edges in a complete graph KnK_n grows quadratically as n(n−1)2\frac{n(n-1)}{2}, providing a quick reference for small instances as shown below.
nnEdges in KnK_n
10
21
33
46
510
615
721
828
936
1045
1155
1266

Real-World Applications

Complete graphs serve as foundational models in network design, particularly for representing fully connected topologies such as full mesh networks in . In these systems, every node connects directly to every other node, ensuring high and low latency for data transmission, which is critical for applications like backbone infrastructure in wide-area networks. For instance, full mesh configurations are employed in scenarios requiring robust , where the complete connectivity of the graph KnK_n minimizes single points of failure by providing multiple alternative paths between any pair of nodes. In and optimization, complete graphs form the basis for , which determines the maximum number of edges in a graph without a complete subgraph KrK_r, guiding the design of extremal structures in problems like and scheduling. This theorem underpins applications in , such as approximating solutions to the maximum or avoiding forbidden substructures in network routing algorithms to maximize efficiency without inducing dense bottlenecks. Seminal work by Paul Turán established this framework, influencing high-impact areas including error-correcting codes and geometric packing problems where avoiding complete subgraphs optimizes space or capacity. In within , complete graphs model cliques, representing tightly knit groups where every member maintains direct ties to all others, such as close-knit communities or professional circles that facilitate information flow and social cohesion. These structures are analyzed to identify subgroups influencing behavior, like peer groups in organizational studies, where the density of connections in a KnK_n subgraph highlights mutual acquaintance and trust. Research emphasizes cliques as key units for understanding , with maximal cliques revealing core alliances that propagate norms or innovations across larger networks. Computationally, generating a complete graph KnK_n is efficiently achieved by constructing its , where all off-diagonal entries are set to 1 and the diagonal to 0, requiring a straightforward double loop over the n×nn \times n matrix that runs in O(n2)O(n^2) . This approach is standard in graph libraries and algorithms for initializing dense networks, enabling rapid setup for simulations in optimization or tasks involving fully connected models. The quadratic time reflects the inherent density of (n2)\binom{n}{2} edges, making it scalable for moderate nn in practical implementations.

References

  1. https://mathworld.wolfram.com/CompleteGraph.html
  2. https://www.coconino.edu/resources/files/pdfs/academics/arts-and-sciences/MAT142/Chapter_6_GraphTheory.pdf
  3. https://math.arizona.edu/~kglasner/math443/BondyMurtyGTWA.pdf
  4. https://discrete.openmathbooks.org/dmoi3/sec_gt-intro.html
  5. https://math.gordon.edu/courses/mat230/handouts/graphs.pdf
  6. https://www.csd.uwo.ca/~abrandt5/teaching/DiscreteStructures/Chapter7/graphs.html
  7. https://www.sciencedirect.com/science/article/pii/S0315086025000011
  8. https://www3.nd.edu/~dgalvin1/60610/60610_S09/60610graphnotation.pdf
  9. https://www.math.ucsd.edu/~gptesler/154/slides/154_intro_graphs_20-handout.pdf
  10. https://mathworld.wolfram.com/GraphComplement.html
  11. https://diestel-graph-theory.com/
  12. https://openstax.org/books/contemporary-mathematics/pages/12-2-graph-structures
  13. https://oeis.org/A000217
  14. https://cseweb.ucsd.edu/~dakane/Math154/154-textbook.pdf
  15. https://roam.libraries.psu.edu/system/files/e-books/MATH485-Graph_Theory.pdf
  16. https://math.arizona.edu/~kglasner/math443/BondyMurtyGTWA.pdf/05:_Graph_Theory/5.02:_Properties_of_Graphs
  17. https://www.networkpages.nl/handshake-lemma-degrees-in-graphs/
  18. https://www.imsc.res.in/~vikram/DiscreteMaths/2011/connectivity.pdf
  19. https://mathweb.ucsd.edu/~gmckinley/154_sp22/154-notes-2021.pdf
  20. https://mathworld.wolfram.com/Girth.html
  21. https://mathworld.wolfram.com/IndependenceNumber.html
  22. https://mathworld.wolfram.com/PerfectGraph.html
  23. https://arxiv.org/pdf/1810.08734
  24. https://arxiv.org/pdf/1512.07655
  25. https://arxiv.org/abs/2001.02665
  26. https://people.computing.clemson.edu/~goddard/texts/graphTheory/chap3.pdf
  27. https://faculty.etsu.edu/gardnerr/5340/notes-Bondy-Murty-GT/Bondy-Murty-GT-10-5.pdf
  28. https://math.uchicago.edu/~may/REU2017/REUPapers/Xu%2CYifan.pdf
  29. https://oeis.org/A000241
  30. https://mathworld.wolfram.com/ZarankiewiczsConjecture.html
  31. https://www.combinatorics.org/files/Surveys/ds21/ds21v3-2017.pdf
  32. https://mathworld.wolfram.com/GuysConjecture.html
  33. https://mathworld.wolfram.com/Simplex.html
  34. https://mathworld.wolfram.com/CsaszarPolyhedron.html
  35. https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.3190070410
  36. https://mathworld.wolfram.com/TetrahedralGraph.html
  37. https://mathworld.wolfram.com/UtilityGraph.html
  38. https://sites.pitt.edu/~dtipper/2110/Slides4.pdf
  39. https://people.math.ethz.ch/~sudakovb/turan100-talk.pdf
  40. https://www.comm.utoronto.ca/~frank/notes/turan.pdf
  41. https://faculty.ucr.edu/~hanneman/nettext/C11_Cliques.html
  42. https://methods.sagepub.com/book/mono/social-network-analysis-scott-3e/chpt/6-components-cores-cliques
  43. https://www.baeldung.com/cs/adjacency-matrix-list-complexity
Add your contribution
Related Hubs
User Avatar
No comments yet.