Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree

Depends on

• A finite simple graph is a finite vertex set together with a set of two-element vertex subsets
• The cardinality $\lvert A\rvert$ of a finite set

Used by

• A c-sparse set X satisfies α(G[X])≥|X|/(c|X|+1), and a c-dense set satisfies ω(G[X])≥|X|/(c|X|+1) Corollary
• A finite graph on at least k+1 vertices is k-connected if and only if every two vertices have k internally disjoint paths Corollary
• Every nonnull simple planar graph has a vertex of degree at most five Corollary
• Every tree with at least two vertices has at least two leaves Corollary
• K₄ is Hamiltonian but has no Euler circuit Counterexample
• The class of regular graphs is not hereditary Counterexample
• Two dense lobes meeting at one cut vertex give κ(G)=1<λ(G)=2<δ(G)=3 Counterexample
• Two disjoint copies of Kₘ show that Dirac's bound cannot be lowered to n/2-1 for even n=2m≥4 Counterexample
• Two triangles sharing one vertex form a connected simple graph with all degrees even that is not a cycle Counterexample
• A decomposition of a graph's edge set into complete bipartite subgraphs Definition
• Bipartite neighbourhoods, Hall's condition and systems of distinct representatives Definition
• c-sparse, c-dense and c-restricted vertex sets Definition
• Clique, independent set, and vertex cover decision problems Definition
• Co-leaves of a finite graph Definition
• Dominating sets in a finite graph Definition
• Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs Definition
• Modules of a graph, and the trivial modules Definition
• Sparsity of one vertex set to another, and weak sparsity of a pair Definition
• Substituting one graph for a vertex of another Definition
• The Bondy-Chvatal closure of a finite simple graph Definition
• The Laplacian matrix of a finite simple graph Definition
• The line graph whose vertices are the edges of the original graph and whose adjacency records a shared endpoint Definition
• The three-colourability decision problem Definition
• Trees, forests, leaves and isolated vertices Definition
• Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges Definition
• K₄ with one new vertex adjacent to two clique vertices satisfies Ore's condition but not Dirac's condition Example
• Pₙ is prime for every n≥4 Example
• The dihedral group of order eight has Cayley graphs that are a cycle of length eight and a cube Example
• FALSE: a connected simple graph in which every vertex has even degree must itself be a cycle False statement
• FALSE: a finite simple graph is determined up to isomorphism by its degree sequence False statement
• A dense bipartite side has a small hitting set Lemma
• A set is c-sparse exactly when the maximum degree of the graph it induces is at most c times its size Lemma
• A set is c-sparse in G exactly when it is c-dense in Ḡ, so c-restrictedness is complement-invariant Lemma
• A sparse graph either sparsifies further or yields a comb or a large sparse pair Lemma
• A sparse graph without a large sparse pair has a large nearly covered sparse pair Lemma
• A sparse P₅-free graph has a large nearly covered sparse pair Lemma
• A sparse P₅-free graph has an anticomplete two-blockade Lemma
• Every nonempty forest has a vertex of degree at most one Lemma
• For every nontrivial connected graph, λ(G)≤δ(G) Lemma
• If nonadjacent u,v in an n-vertex graph satisfy deg(u)+deg(v)≥ n, then adding uv preserves Hamiltonicity in both directions Lemma

…and 18 more results.

Dependency tree · two levels

9 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

• University of Lethbridge, Combinatorics: A Guided Tour, Graphs and Walks (standard reference, not scraped)