A finite simple graph is a finite vertex set together with a set of two-element vertex subsets

Depends on

• The cardinality $\lvert A\rvert$ of a finite set

Used by

• There are 2^C(n, 2) simple graphs on a fixed labelled n-element vertex set Corollary
• A bipartite graph and a proper two-colouring of its vertices Definition
• A decomposition of a graph's edge set into complete bipartite subgraphs Definition
• Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree Definition
• An oriented incidence matrix of a finite simple graph Definition
• c-sparse, c-dense and c-restricted vertex sets Definition
• Clique, independent set, and vertex cover decision problems Definition
• Cliques, independent sets, clique number and independence number Definition
• Cliques, stable sets, the clique number ω(G) and stability number α(G) Definition
• Cographs by the singleton, disjoint-union, and complete-connection recursion Definition
• Degree in a multigraph, indegree and outdegree in a digraph, and their underlying connectivity Definition
• Directed and undirected Hamiltonian path and cycle decision problems Definition
• Edge counts and densities between nonempty vertex sets Definition
• Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs Definition
• Empty and complete graphs, complete bipartite graphs, and the convention that Pₙ and Cₙ have n vertices Definition
• Graph edit distance and being ε-far from an induced-hereditary property Definition
• Graph isomorphisms, automorphisms and graph complements Definition
• Hamilton paths, Hamilton cycles, Hamiltonian graphs and Hamilton-connected graphs Definition
• Induced embeddings and induced copies of a graph Definition
• Matchings, saturated vertices, maximal and maximum matchings, perfect matchings and ν(G) Definition
• Modular partitions and the quotient graph they define Definition
• Modules of a graph, and the trivial modules Definition
• Multigraphs, loops and directed graphs as variants distinct from the default finite simple graph Definition
• Ordinary-subgraph extremal number ex(n,H), Turán graph T_n,r, and balanced blowup H[s] Definition
• Plane embeddings of finite simple graphs, their faces, facial boundary walks and lengths (counting a bridge twice), and planar graphs Definition
• Prime graphs: those whose only modules are the trivial ones Definition
• Proper vertex colourings and chromatic number Definition
• Simple graphs on an arbitrary vertex set Definition
• Sparsity of one vertex set to another, and weak sparsity of a pair Definition
• Subgraphs, induced subgraphs and spanning subgraphs Definition
• Substituting one graph for a vertex of another Definition
• The adjacency matrix of a finite simple graph Definition
• The Bondy-Chvatal closure of a finite simple graph Definition
• The bull graph Definition
• The complete connection of two disjoint graphs Definition
• The Erdős-Rényi finite random graph G(n,p) Definition
• The line graph whose vertices are the edges of the original graph and whose adjacency records a shared endpoint Definition
• The Petersen graph on the two-element subsets of a five-element set, adjacent when disjoint Definition
• The star-expansion of a graph Definition
• The three-colourability decision problem Definition

…and 18 more results.

Dependency tree · two levels

8 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

• R. Diestel, Graph Theory, Chapter 1 preview (standard reference, not scraped)