Graph Theory

Diestel, R. (2017). Graph Theory. Springer.

Type

Book

Intellectual base

Review or monograph

Year

2017

DOI

10.1007/978-3-662-53622-3

ISBN

9783662536216

DOI registrant

Springer Nature

Link

https://doi.org/10.1007/978-3-662-53622-3

Cited from

mathematics

Cited by

10 citations across 10 artifacts.

Each citation links to the sentence it supports in the citing article.

Primes

• Cycle
  • The cycle supports several reusable inference patterns, each stated in terms of closed paths rather than any substrate. Cycle space: the cycles of a graph form a vector space over the two-element field whose dimension is edges minus vertices plus components, giving a structural counting principle and a basis for cycle decomposition.

    This sourceEstablishes the cycle space of a graph as a vector space over GF(2) of dimension (edges − vertices + components), giving the cycle-counting principle and a basis for cycle decomposition.

Domain-specific

• Clique (Graph Theory)
  • Equivalently, the subgraph induced by \(C\) is complete.
• Clique-sum
  • A clique-sum is a graph-composition operation that takes the disjoint union of two graphs and identifies corresponding vertices of selected equal-order cliques, with interface-edge deletion governed by the chosen convention.
• Dense Graph
  • For a graph sequence, the clean asymptotic regime is \(|E|=\Theta(n^2)\), equivalently density bounded away from zero along the sequence.
• Girth (Graph Theory)
  • Large girth means neighborhoods remain tree-like to a larger radius even when the graph eventually contains cycles.
• Graph Invariant
  • Listed in the references but not attached to a specific claim.
• Hadwiger number
  • Hadwiger number is the largest integer k such that the complete graph on k vertices occurs as a minor of a given undirected graph.
• Planarity
  • Every connected planar graph with V vertices, E edges, and F faces satisfies Euler's formula V − E + F = 2, which immediately bounds the edge density (E ≤ 3V − 6 for simple planar graphs, E ≤ 2V − 4 when triangles are also excluded), explaining why planar graphs are sparse; planarity itself, not sparsity alone, makes some problems that are NP-hard in general (such as max-cut) polynomial on planar graphs, while others (such as Hamiltonian cycle) stay NP-complete

    This sourceProves Euler's formula for connected plane graphs and the resulting bound of at most 3n − 6 edges, tighter for triangle-free graphs.

    Supported in partVerified against the source

    Read by an automated reader; not a human review. How support was checked

• Quotient Graph
  • Diestel's treatment of contractions and minors supplies the standard connected-block special case.
• Tree (Set Theory)
  • An ordinary graph edge cannot encode that limit connection without adding different structure.

    This sourceAuthoritative source for the connected-acyclic graph-tree identity used to mark the graph-theoretic boundary.

Verification

Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.

Does it back the claim? Read against the text for 1 of 10 citations: 1 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.

Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.

See how references were verified.

Links previously used in the corpus

Before the registry existed this work was also linked 1 other way.

• https://diestel-graph-theory.com/ ×1

Registry ID ref:963be57f22ca · see in the full table