Title: Theory / Unimportant / CS / Fundamental / Graph / Reinhard Diestel/{
Tags: fromMath mathToDef mathToSee automaticImplies hasSeenConjDef TypToQuestion toBinaryRelation defToQuestion toBinaryFunction

Definition: \(i+n\mathbb Z\).
Page: 001
Chapter: 1
Variables: \(i\in\mathbb N\).
Context: \(\mathbb Z/n\mathbb Z\)
Notation: \(\overline i\)

Definition: The greatest integer smaller than \(x\).
Page: 001
Chapter: 1
Variables: \(x\in\mathbb R\)
Notation: \(\lfloor x\rfloor\)

Name: The least integer greater than \(x\)
Page: 001
Chapter: 1
Variables: \(x\in\mathbb R\)
Notation: \(\lceil x\rceil\)

Q: \(\mathcal A'\) [...] the partition \(\mathcal A\) if [...]
A: refines; all \(A'_i\in \mathcal A'\) is a subset of some \(A_j\in\mathcal A\)
Page: 001
Chapter: 1
Variables: \(A\) a set
\(\mathcal{A,A}'\) two partitions of \(A\).

Name: The set of \(k\)-sets
Definition: The set of \(k\)-element subsets of \(A\).
Page: 001
Chapter: 1
Variables: \(A\) be a set and \(k\in\mathbb N\).
Notation: \([A]^k\)

Name: A graph
Definition: A pair \((V,E)\) of sets such that \(E\subseteq[V]^2\).
Page: 002
Chapter: 1
Denoted by: G

Name: A vertex
Definition: An element of \(V\).
Page: 002
Chapter: 1
Variables: \(G=(V,E)\) be a graph.
Name2: A node
Name3: A point

Name: An edge
Definition: The elements of \(E\).
Page: 002
Chapter: 1
Variables: \(G=(V,E)\) be a graph.
Name2: A line

Name: A graph on \(V\)
Definition: A graph whose set of vertices is \(V\).
Page: 002
Chapter: 1
Variables: \(V\) a set

Name: The vertex set of \(G\).
Page: 002
Chapter: 1
Variables: \(G=(V,E)\) be a graph.
Notation: \(V(G)\)

Definition: The edge set of \(G\).
Page: 002
Chapter: 1
Variables: \(G=(V,E)\) be a graph.
Notation: \(E(G)\)

Name: The order of \(G\)
Definition: \(|V|\).
Page: 002
Chapter: 1
Variables: \(G=(V,E)\) be a graph.
Notation: \(|G|\)

Definition: \(|E|\).
Page: 002
Chapter: 1
Variables: \(G=(V,E)\) be a graph.
Notation: \(\parallel G\parallel\)

Name: Finite graph
Definition: A graph whose order is finite.
Page: 002
Chapter: 1
Variables: \(G=(V,E)\) be a graph.

Name: an infinite graph
Definition: A graph whose order is infinite
Page: 002
Chapter: 1
Variables: \(G=(V,E)\) be a graph.

Name: A countable graph
Definition: A graph whose order is countable.
Page: 002
Chapter: 1
Variables: \(G=(V,E)\) be a graph.

Definition: The graph \((\emptyset,\emptyset)\)
Page: 002
Chapter: 1
Notation: The graph \(\emptyset\)

Name: A trivial graph
Definition: A graph whose order is 0 or 1.
Page: 002
Chapter: 1

Name: Some thing incident to \(e\)
Definition: A vertices belonging to \(e\).
Page: 002
Chapter: 1
Variables: \(G=(V,E)\) be a graph,
\(v\in V\)
\(e\in E\).
Definition2: \(e\) is an edge at \(v\).

Name: The ends of \(e\)
Definition: The elements of \(e\)
Page: 002
Chapter: 1
Variables: \(G=(V,E)\) be a graph
\(e\in E\).

Definition: joins \(x\) and \(y\).
Page: 002
Chapter: 1
Variables: \(G=(V,E)\) be a graph, \(x,y\in V\)
Context: \(\{x,y\}\). It
Notation: \(xy\) or \(yx\)

Name: An \(X-Y\) edge
Definition: An edge between an element of \(X\) and \(Y\).
Page: 002
Chapter: 1
Variables: \(G=(V,E)\) be a graph,
\(X,Y\subseteq V\)

Definition: The set of all \(X-Y\) edges
Page: 002
Chapter: 1
Variables: \(G=(V,E)\) be a graph,
\(X,Y\subseteq V\)
Notation: \(E(X,Y)\)

Definition: The set of all the edges in \(E\) at a vertex \(v\).
Page: 002
Chapter: 1
Notation: \(E(v)\)

Name: adjacent vertices
Definition: Two vertices such that \(\{x,y\}\) is an edge of \(G\)
Page: 003
Chapter: 1
Name2: Neighbours vertices

Name: Adjacent edges
Definition: Edges which have an end in common.
Page: 003
Chapter: 1

Name: A complete graph
Definition: A graph whose all vertices are pairwise adjacent.
Page: 003
Chapter: 1
Name2: A clique

Name: \(K^n\)
Definition: A complete graph on \(n\) vertices.
Page: 003
Chapter: 1

Name: A triangle
Page: 003
Chapter: 1
Notation: \(K^3\)

Name: Independant vertices or edges
Definition: Pairwise non-adjacent vertices or edges.
Page: 003
Chapter: 1
Variables: \(G\) a graph

Name: An independant set
Definition: A set of pair of independant elements.
Page: 003
Chapter: 1
Variables: \(G\) a graph

Name: Stable sets
Definition: Independent sets of vertices.
Page: 003
Chapter: 1
Variables: \(G\) a graph

Name: A homomorphism from \(G\) to \(G'\)
Definition: A map \(\phi:V\to V'\) which preserves the adjacency of vertices, that is, if \(\{\phi(x),\phi(y)\}\in E'\) whenever \(\{x,y\}\in E\).
Page: 003
Chapter: 1
Variables: \(G=(V,E)\), \(G'=(V',E')\) be two graphs.

Question: Then \(\phi^{-1}(x')\) is
Answer: an independent set of vertices in \(G\).
Page: 003
Chapter: 1
Variables: \(G=(V,E)\), \(G'=(V',E')\) be two graphs and \(\phi:G\to G'\) be an homomorphism. Let \(x'\in V'\).

Name: An isomorphism of graph
Definition: A surjective homomorphism whose inverse is a homomorphism.
Page: 003
Chapter: 1

Name: An automorphism of \(G\)
Definition: A morphism from \(G\) to itself.
Page: 003
Chapter: 1
Variables: \(G\) a graph

Page: 003
Definition: A pair of graphs such that there exists an isomorphism \(\phi:G\to G'\).
Chapter: 1
Variables: \(G,G'\) two graphs
Name: Isomorphic graphs
Context: Graph

Page: 003
Definition: \(G\) and \(G'\) are isomorphic graphs
Chapter: 1
Variables: \(G,G'\) two graphs
Notation: \(G\simeq G'\)
Context: Graph

Name: An abstract graph
Definition: An isomorphism class of graph.
Page: 003
Chapter: 1

Name: A graph property
Definition: A class of graphs that is closed under isomorphism.
Page: 003
Chapter: 1

Name: Disjoint graphs
Definition: Graph \(G\) and \(G'\) such that \(G\cap G'=\emptyset\)
Page: 004
Chapter: 1
Index: first line

Name: \(G\) is a subgraph of \(G'\)
Definition: \(V'\subseteq V\) and \(E'\subseteq E\).
Page: 004
Chapter: 1
Variables: \(G,G'\) two graphs
Notation: \(G\subseteq G'\)
Name2: \(G'\) is a supergraph of \(G\)

Definition: \(G\subseteq G'\) and \(G\ne G'\).
Page: 004
Chapter: 1
Variables: \(G,G'\) two graphs
Notation: \(G\subsetneq G'\)

Name: An induced subgraph of \(G\)
Definition: \(G[V']\) for some \(V'\subseteq V\)
Page: 004
Chapter: 1
Variables: \(G\) be two graphs.

Name: The subgraph induced by \(V'\)
Definition: A graph \(G'\subseteq G\) such that \(G'\) contains exactly the edges \(xy\in E\) with \(x,y\in V'\)
Page: 004
Chapter: 1
Variables: \(G\) be two graphs.
\(V'\subseteq V\)
Notation: \(G[V']\)
Name2: The subgraph spanned by \(V'\)

Name: \(G[U]\)
Definition: The graph on \(U\) whose edges are precisely the edges of \(G\) with both ends in \(U\).
Page: 004
Chapter: 1
Variables: \(G\) be a graph and \(U\subseteq V\).

Definition: \(G[V(H)]\).
Page: 004
Chapter: 1
Variables: \(G\) be a graph
\(H\subseteq V\).
Notation: \(G[H]\)

Definition: \(G[V\setminus U]\).
Page: 004
Chapter: 1
Variables: \(G\) be a graph and \(U\) is a set of vertices.
Notation: \(G-U\)

Definition: \(G-\{v\}\).
Page: 004
Chapter: 1
Variables: \(G\) be a graph and \(v\) a vertex.
Notation: \(G-v\)

Name: \(G-G'\)
Definition: \(G-V(G')\).
Page: 004
Chapter: 1
Variables: \(G\) be a graph
\(G'\subseteq G\) a subgraph.

Name: \(G+F\)
Definition: \((V,E\cup F)\).
Page: 004
Chapter: 1
Variables: \(G\) be a graph
\(F\subseteq[V]^2\)

Definition: \((V,E\setminus F)\).
Page: 004
Chapter: 1
Variables: \(G\) be a graph
\(F\subseteq[V]^2\).
Notation: \(G-F\)

Name: An edge-maximal graph with \(P\)
Definition: A graph \((V,E)\) which satisfies \(P\) such that no graph \((V,F)\) with \(F\supsetneq E\) does.
Page: 004
Chapter: 1
Variables: \(P\) be a graph property.

Definition: \((V\cup V',E \cup E')\).
Page: 004
Chapter: 1
Variables: \(G,G'\) be two graphs with \(V\cap V'=\emptyset\).
Notation: \(G\star G'\)

Name: The complement of \(G\)
Definition: \((V,[V]^2\setminus E)\).
Page: 004
Chapter: 1
Variables: \(G\) be a graph.
Notation: \(\overline G\)

Name: The line graph of \(G\)
Definition: The graph on \(E\) in which \(x,y\in E\) are adjacent as vertices if and only if they are adjacent as edges in \(G\).
Page: 004
Chapter: 1
Variables: \(G\) be a graph.
Notation: \(L(G)\)

Name: The set of neighbours of \(v\) in \(G\).
Page: 005
Section: 2
Variables: \(G=(V,E)\) be a non-empty graph.
\(v\in V\).
Notation: \(N_G(v)\)
Notation2: \(N(v)\)

Definition: The set of neighbour of \(U\) in \(G\), not in \(U\).
Page: 005
Section: 2
Variables: \(G=(V,E)\) be a non-empty graph. Let \(U\subseteq V\).
Notation: \(N(U)\)

Name: The degree of \(v\)
Definition: \(|E(v)|\); the number of neighboors of \(v\).
Page: 005
Section: 2
Variables: \(G=(V,E)\) be a non-empty graph
\(v\subseteq V\).
Notation: \(d_G(v)\)
Name2: The valency of \(v\)
Notation2: \(d(v)\)

Name: An isolated vertex
Definition: A vertex of degree 0.
Page: 005
Section: 2
Variables: \(G=(V,E)\) be a non-empty graph.
\(v\subseteq V\).

Name: The maximum degree of \(G\)
Page: 005
Section: 2
Variables: \(G=(V,E)\) be a non-empty graph.
Notation: \(\Delta(G)\)

Name: \(i\)-regular graph
Definition: A non-empty graph whose all vertices have degree \(i\).
Page: 005
Section: 2
Variables: \(i\in\mathbb N\).

Name: Regular graph
Definition: An \(i\)-regular graph for some \(i\in\mathbb N\).
Page: 005
Section: 2
Variables: \(G=(V,E)\) be a non-empty graph.

Name: Cubic graph
Definition: \(3\)-regular graph.
Page: 005
Section: 2
Variables: \(G=(V,E)\) be a non-empty graph.

Name: The average degree of \(G\)
Definition: \(\frac{\sum_{v\in V} d(v)}{|V|}\)
Page: 005
Section: 2
Variables: \(G=(V,E)\) be a non-empty graph
Notation: \(d(G)\)
Definition2: \(2\epsilon(G)\)

Smaller0: \(\delta(G)\)
Greater0: \(d(G)\)
Page: 005
Section: 2
Variables: \(G=(V,E)\) be a non-empty graph.
Smaller to greater: \(\le\)
Greater to smaller: \(\ge\)
Greatest: \(\Delta(G)\)

Name: The edge/vertices ratio
Definition: \(\frac{d(G)}{2}\)
Page: 005
Section: 2
Variables: \(G=(V,E)\) be a non-empty graph.
Notation: \(\epsilon(G)\)

Question: The number of vertices of odd degree of \(G\) is
Answer: even.
Page: 005
Chapter: 1
Section: 2
Variables: \(G=(V,E)\) be a non-empty graph.
Kind: Proposition

Question: \(G\) has a subgraph \(H\) such that
Answer: \(\delta(H)>\epsilon(H)\ge\epsilon(G)\).
Page: 006
Chapter: 1
Section: 2
Variables: \(G=(V,E)\) be a non-empty graph.
Kind: Proposition
Assuming: \(E\) is not-empty

Name: A path
Definition: A non-empty graph \(P=(V,E)\) of the form \(V=\{x_0,\dots,x_k\}\) and \(E=\{x_0x_1,\dots,x_{k-1}x_k\}\) where the \(x_i\) are distinct.
Page: 006
Section: 3
Context: Graph

Name: The length of \(P\)
Definition: The number of edges of a path.
Page: 006
Section: 3
Variables: \(P\) be a path.

Question: The edges \(x_0\) and \(x_k\) are said to be
Answer: linked by \(P\).
Page: 006
Section: 3
Variables: \(P=(\{x_0,\dots,x_k\},\{x_0x_1,\dots,x_{k-1}x_k\})\) be a path.

Name: Endvertices
Definition: The edges \(x_0\) and \(x_k\).
Page: 006
Section: 3
Variables: \(P=(\{x_0,\dots,x_k\},\{x_0x_1,\dots,x_{k-1}x_k\})\) be a path.
Context: Path, graph
Name2: Ends

Definition: \((\{x_0,\dots,x_k\},\{x_0x_1,\dots,x_{k-1}x_k\})\).
Page: 007
Section: 3
Context: Graph
Notation: \(x_0\dots x_k\)

Definition: \(x_0\dots x_i\) (resp, \(x_i\dots x_k\)).
Page: 007
Section: 3
Variables: \(P=x_0\dots x_k\).
Notation: \(Px_i\) (resp. \(x_iP\))

Definition: \(x_0\dots x_{i-1}\) (resp, \(x_{i+1}\dots x_k\)).
Page: 007
Section: 3
Variables: \(P=x_0\dots x_k\).
Notation: \(P\mathring{x_i}\) (resp. \(\mathring{x_i}P\))

Definition: \(x_1\dots x_{k-1}\).
Page: 007
Section: 3
Variables: \(P=x_0\dots x_k\).
Notation: \(\mathring{P}\)

Q: [...] is [...].
A: \(PxQ\); the path \(Px\cup xQ\)
Page: 007
Section: 3
Variables: \(P\) and \(Q\) be path containing the edge \(x\).

Name: A cycle
Definition: A graph of the form \((\{x_i\mid i<k\}, \{x_i,x_{i+1\mod k}\})\)
Page: 008
Section: 3
Denoted by: \(C\)

Q: [...] is an abbreviation for \([...]\).
A: \(P=x_0\dots x_kx_0\); P=(\{x_0,\dots,x_k\},\{x_0x_1,\dots,x_{k-1}x_k,x_kx_0\})
Page: 008
Section: 3

Name: The length of \(C\)
Definition: the number of vertices of \(C\)
Page: 008
Section: 3
Variables: \(C\) be a cycle.
Definition2: the number of edges of \(C\)

Definition: The cycle of length \(k\).
Page: 008
Section: 3
Context: Graph
Notation: \(C^k\)

Name: The girth of \(G\)
Definition: The minimum length of a cycle in \(G\) (and \(\infty\) if there are no cycles).
Page: 008
Section: 3
Variables: \(G\) be a graph.
Abbreviation: \(g(G)\)

Name: The circumference of \(G\)
Definition: The maximal length of a cycle in \(G\) (and \(0\) if there are no cycle)
Page: 008
Section: 3
Variables: \(G\) be a graph.

Name: A chord of \(C\)
Definition: An edge \(e\in E\setminus C\) whose ends belong to \(C\).
Page: 008
Section: 3
Variables: \(G=(V,E)\) a graph
\(C\) a cycle in \(G\)

Name: An induced cycle in \(G\)
Definition: A cycle in \(G\) without cord.
Page: 008
Section: 3
Variables: \(G\) a graph.

Smaller0: \(\delta(G)\ge2\)
Greater0: \(\delta(G)\)
Page: 008
Chapter: 1
Section: 3
Variables: \(G\) be a graph.
Kind: Proposition
Prefix Greater: \(G\) contains a path of length
Greater1: \(\delta(G)+1\)
Connect Greater0: and a cycle of length

Page: 008
Section: 3
Notation: \(d_G(x,y)\)
Variables: \(G\) be a graph and \(x,y\) two vertices.
Name: The distance between \(x\) and \(y\)
Definition: The length of the shortest \(x-y\) path in \(G\). Or \(\infty\) if no such path exists.

Name: The diameter of \(G\)
Definition: The greatest distance between two elements of \(G\).
Page: 008
Section: 3
Variables: \(G\) be a graph.

Name: A central vertex
Definition: A vertex whose distance from any other vertex is as small as possible.
Page: 008
Section: 3
Variables: \(G\) be a graph
\(v\) a vertex

Name: The radius of \(G\)
Definition: The maximal distance between a vertex and a central vertex.
Page: 008
Section: 3
Variables: \(G\) be a graph.
Abbreviation: \(\text{rad}(G)\)

Smaller0: \(\text{rad}(G)\)
Greater0: \(\text{diam}(G)\)
Page: 008
Section: 3
Variables: \(G\) be a graph.
Smaller to greater: \(\le\)
Greater to smaller: \(\ge\)

Smaller0: \(\text{diam}(G)\)
Greater0: \(\text{rad}(G)\)
Page: 008
Section: 3
Variables: \(G\) be a graph.
Smaller to greater: \(\le2\)
Suffix Smaller: \(\ge\frac12\times\)

Smaller0: its radius is at most \(k\)
Greater0: less than \(\frac{d(d-1)^k}{d-2}\)
Page: 009
Chapter: 1
Section: 3
Variables: \(G\) be a graph. \(d,g\in\mathbb N\).
Kind: Proposition
Hide middle: yes
Prefix Greater: G has
Smaller1: maximum degree at most \(d\ge3\)
Suffix Greater: vertices

Smaller0: \(d(G)\ge d\ge 2\) and \(g(G)\ge g\in \mathbb N\)
Greater0: :
-\(1+d\sum_{i=0}^{r-1}(d-1)^i\) if \(g\) is of the form \(2r+1\),
-\(2\sum_{i=0}^{r-1}(d-1)^i\) if \(g\) is of the form \(2r\)
Page: 010
Chapter: 1
Section: 3
Variables: \(G\) be a graph, \(d,g\in\mathbb N\).
Index: 4
Kind: Theorem
Hide middle: yes
Prefix Greater: \(|G|\) is at least
Extra: Too complicated

Smaller0: \(d(G)\ge 3\)
Greater0: \(<2\log{|G|} \)
Page: 010
Chapter: 1
Section: 3
Variables: \(G\) be a graph.
Index: 5
Kind: Corollary
Hide middle: yes
Prefix Greater: \(g(G)\)

Name: A walk (of length \(k\)) in \(G\)
Definition: A sequence \(v_0e_0v_1\dots e_{k-1}v_k\) where \(e_i=\{v_i,v_{i+1}\}\).
Page: 010
Chapter: 1
Section: 3
Variables: \(G\) be a graph and \(k\in\mathbb N\)

Name: Connected graph
Definition: A non-empty graph such that any two vertices are linked by a path.
Page: 010
Chapter: 1
Section: 4

Name: Connected set of vertices
Definition: A set \(U\) of vertices such that \(G[U]\) is connected.
Page: 010
Chapter: 1
Section: 4
Variables: \(G\) be a graph.

Name: A disconnected graph
Definition: A graph which is not connected.
Page: 010
Chapter: 1
Section: 4

Question: There exists an enumeration of the vertices \(v_1,\dots,v_n\) such that
Answer: \(G[v_1,\dots,v_n]\) is connected for every \(i\le n\).
Page: 010
Chapter: 1
Section: 4
Variables: \(G\) be a graph with \(n\) vertices.
Kind: Proposition
Assuming: \(G\) is connected
Construction: By induction. Choose a first vertex \(v_1\). At stage \(n\), choose a vertex connected to some \(v_i\) for \(i<n\).

Name: A component of \(G\)
Definition: A maximal connected subgraph of \(G\).
Page: 011
Variables: \(G=(V,E)\) a graph.

Question: The set of component of \(G\).
Answer: A partition of \(G\)
Page: 011
Chapter: 1
Section: 4
Variables: \(G=(V,E)\) a graph.
Index: 11

Name: \(X\) separates \(A\) and \(B\)
Definition: Every \(A-B\) path in \(G\) contains a vertex or an edge from \(X\).
Page: 011
Chapter: 1
Section: 4
Variables: \(G=(V,E)\) a graph,
\(A,B\subseteq V\)
\(X\subseteq V\cup E\).
Index: 11

Name: \(X\) separates \(a\) and \(b\)
Definition: \(X\) separates \(\{a\}\) and \(\{b\}\) and \(a,b\not\in X\).
Page: 011
Chapter: 1
Section: 4
Variables: \(G=(V,E)\) a graph,
\(a,b\in V\)
\(X\subseteq V\cup E\).
Index: 11

Name: \(X\) separates \(G\)
Definition: \(X\) separates two vertices in \(G\).
Page: 011
Chapter: 1
Section: 4
Variables: \(G=(V,E)\) a graph
\(X\subseteq V\cup E\).
Index: 11

Name: A cutvertex
Definition: A vertex which separates two other vertices of the same component.
Page: 011
Chapter: 1
Section: 4
Variables: \(G=(V,E)\) a graph, and \(v\in V\).
Index: 11

Name: A bridge
Definition: An edge which separates its ends.
Page: 011
Chapter: 1
Section: 4
Variables: \(G=(V,E)\) a graph.
Index: 11

Smaller0: a bridge
Greater0: does not lie on any cycle
Page: 011
Chapter: 1
Section: 4
Variables: \(G=(V,E)\) a graph, and \(e\in E\).
Index: 11
Smaller to greater: iff
Hide middle: yes
Prefix Greater: \(e\)
Prefix Smaller: \(e\) is

Name: A separation of \(G\)
Definition: \(A\cup B=V\) and \(G\) has no edge between \(A\setminus B\) and \(B\setminus A\).
Page: 011
Chapter: 1
Section: 4
Variables: \(G=(V,E)\) a graph.
Index: , 11
Definition2: \(A\cap B\) separates \(A\) from \(B\)
Conjdef: A pair \(A,B\subseteq V\) such that, equivalently

Name: The order of the separation \(\{A,B\}\)
Definition: \(|A\cap B|\).
Page: 011
Chapter: 1
Section: 4
Variables: \(G=(V,E)\) a graph
\(A,B\subseteq V\) a separation
Index: 11

Name: The sides of the separation \(\{A,B\}\)
Definition: \(A\) and \(B\).
Page: 011
Chapter: 1
Section: 4
Variables: \(G=(V,E)\) a graph, and
\(A,B\subseteq V\) a separation.
Index: 11

Name: \(k\)-connected graph
Definition: A graph \(G\) such that \(|G|>k\) and \(G-X\) is connected for every \(X\subseteq V\) with \(|X|<k\).
Page: 011
Chapter: 1
Section: 4
Variables: \(k\in\mathbb N\).
Index: 11

Name: The connectivity of \(G\)
Definition: The greatest \(n\) such that \(G\) is \(n\)-connected.
Page: 011
Chapter: 1
Section: 4
Variables: \(G=(V,E)\) a graph.
Notation: \(\kappa(G)\)
Index: 11

Smaller0: 0
Greater0: disconnected
Page: 012
Chapter: 1
Section: 4
Variables: \(G=(V,E)\) a graph.
Smaller to greater: iff
Prefix Greater: \(G\) is
Greater1: a \(K^1\)
Connect Greater0: or \(G\) is
Prefix Smaller: \(\kappa (G)\) is

Question: \(\kappa (K^n)\) is
Answer: \(n-1\).
Page: 012
Chapter: 1
Section: 4
Variables: \(G=(V,E)\) a graph.

Name: \(k\)-edge-connected graph
Definition: A graph \(G\) with \(|G|>1\) and such that \(G-F\) is connected for every \(F\subseteq E\) with \(|F|<k\).
Page: 012
Chapter: 1
Section: 4
Variables: \(k\in\mathbb N\).

Name: The edge-connectivity of \(G\)
Definition: The greatest \(k\) such that \(G\) is \(k\)-edge-connected.
Page: 012
Chapter: 1
Section: 4
Variables: \(G=(V,E)\) a graph
Notation: \(\lambda(G)\)

Smaller0: \(\kappa(G)\)
Greater0: \(\delta(G)\)
Page: 012
Chapter: 1
Section: 4
Variables: \(G=(V,E)\) a non-trivial graph.
Index: 2
Kind: Proposition
Smaller to greater: \(\le\)
Greater to smaller: \(\ge\)
Hide sides: yes

Smaller0: \(\lambda(G)\)
Greater0: \(\delta(G)\)
Page: 012
Chapter: 1
Section: 4
Variables: \(G=(V,E)\) a non-trivial graph.
Index: 2
Kind: Proposition
Smaller to greater: \(\le\)
Greater to smaller: \(\ge\)

Smaller0: \(d(G)\ge 4k\)
Greater0: a \((k+1)\)-connected subgraph \(H\) such that \(\epsilon(H)>\epsilon(G)-k\)
Page: 012
Chapter: 1
Section: 4
Variables: \(G=(V,E)\) and \(k\in\mathbb N^{>0}\)
Index: 2
Kind: Proposition
Hide middle: yes
Prefix Greater: \(G\) admits

Name: Acyclic graph
Definition: A graph which contains no cycles.
Page: 013
Chapter: 1
Section: 5
Name2: Forest

Name: A tree
Definition: A connected forest.
Page: 013
Chapter: 1
Section: 5
Variables: \(G=(V,E)\).
Kind: Theorem
Definition2: A graph such that, any two vertices are linked by a unique path in \(G\)
Definition3: A minimally connected graph, i.e. \(G\) is connected but \(T-e\) is disconnected for every edge \(e\in E\)
Extra: Cor 3
Definition4: A maximally acyclic graph. I.e. \(G\) is acyclic, but \(T+xy\) is cyclic for any two non-adjacent vertices \(x,y\in G\)
Definition5: A connected graph whose number of vertices is one plus the number of edges

Name: A leaf
Definition: A node of degree 1.
Page: 013
Chapter: 1
Section: 5
Variables: \(G=(V,E)\) a tree

Name: An inner vertex
Definition: A vertex which is not a leaf.
Page: 013
Chapter: 1
Section: 5
Variables: \(G=(V,E)\) a tree.

Q: \(G\) have [number] leaf/ves
A: at least one
Page: 013
Chapter: 1
Section: 5
Variables: \(G=(V,E)\) a tree nonempty.

Smaller0: [$]\delta(G)\ge\abs{T}-1[/$]
Greater0: \(G\) contains a subgraph isomorphic to \(T\)
Page: 015
Chapter: 1
Section: 5
Variables: \(T\) a tree
\(G\) a graph
Index: 4
Kind: Corollary

Definition: The unique path from \(x\) to \(y\) in \(T\).
Page: 014
Chapter: 1
Section: 5
Variables: \(T=(V,E)\) a tree and \(x,y\in V\).
Notation: \(xTy\)

Name: A rooted tree
Definition: A pair \((T,r)\) with \(T=(V,E)\) and \(r\in V\).
Page: 015
Chapter: 1
Section: 5

Name: The root of \(T\)
Definition: \(r\).
Page: 015
Chapter: 1
Section: 5
Variables: \((T,r)\) a rooted tree.

Name: \(x\) lies below \(y\) in \(T\)
Definition: \(x\in rTy\).
Page: 015
Chapter: 1
Section: 5
Variables: \(((V,E),r)\) a rooted tree, \(x,y\in V\).

Name: The up(down)-closure of \(x\)
Definition: \(\{z\mid z\ge x\}\)(\(\{z\mid z\le x\}\)).
Page: 015
Chapter: 1
Section: 5
Variables: \(((V,E),r)\) a rooted tree, \(x\in V\).
Notation: \(\lfloor x\rfloor\)(\(\lceil x\rceil\))

Name: An up-set
Definition: A set \(X\subseteq V\) such that \(\lfloor X\rfloor =X\).
Page: 015
Chapter: 1
Section: 5
Variables: \(((V,E),r)\) a rooted tree
Name2: A set closed upward

Q: Its [...] element(s) is(are) [...].
A: least; \(r\)
Page: 015
Chapter: 1
Section: 5
Variables: \(((V,E),r)\) a rooted tree

Q: Its [...] element(s) is(are) [...].
A: maximal; its leaves
Page: 015
Chapter: 1
Section: 5
Variables: \(((V,E),r)\) a rooted tree

Smaller0: a down-set of a single vertex
Greater0: \(X\) is a chain
Page: 015
Chapter: 1
Section: 5
Variables: \(((V,E),r)\) a rooted tree
\(X\subseteq V\)
Hide middle: yes
Prefix Smaller: \(X\) is

Name: The height of \(x\)
Definition: The distance from \(x\) to \(r\).
Page: 015
Chapter: 1
Section: 5
Variables: \(T=((V,E),r)\) a rooted tree
\(x\in V\)

Name: A tree normal in \(G\)
Definition: A rooted tree contained in \(G\) such that, for each \((v,w)\in E\), \(v\) and \(w\) are comparable in the order generated by \(T\).
Page: 015
Chapter: 1
Section: 5
Variables: \(G=(V,E)\) a graph.
Name2: A depth-first search tree

Smaller0: \(S\) is down-closed
Greater0: spanned by the sets \(\lfloor x\rfloor\) with \(x\) minimal in \(T-S\)
Page: 016
Chapter: 1
Section: 5
Variables: \(G=(V,E)\) a graph, \(T=((V,E'),r)\) a normal spanning tree in \(G\) and \(S\subseteq V\).
Kind: Lemma
Hide middle: yes
Prefix Greater: \(G-S\) is

Question: The number of normal spanning tree with root \(x\) is
Answer: at least one.
Page: 016
Chapter: 1
Section: 5
Variables: \(G=(V,E)\) a graph and \(x\in V\).
Index: 6
Kind: Proposition

Name: \(r\)-partite graph
Definition: A graph \(G\) such that there exists a partition of \(V\) in \(r\) classes such that \((v,w)\in E\) implies that \(v\) and \(w\) belong to distinct classes.
Page: 17
Chapter: 1
Section: 6
Variables: \(r\ge 2\).

Name: Complete multipartite graph
Definition: A graph \(G\) which is \(r\)-multipartite and for each \(v,w\) in distinct classes, \((v,w)\in E\).
Page: 17
Chapter: 1
Section: 6
Variables: \(r\ge 2\)
\(G=(V,E)\) a \(r\)-partite graph.

Definition: \(\overline{K^{n_1} }*\dots*\overline{K^{n_r} }\).
Page: 17
Chapter: 1
Section: 6
Variables: \(r\ge 2\),
\(n_1,\dots,n_r>0\).
Notation: \(K_{n_1,\dots,n_r}\)

Definition: \(K_{n,\dots,n}\) with \(s\) repetitions of \(n\).
Page: 17
Chapter: 1
Section: 6
Variables: \(r\ge 2\), \(s>0\).
Notation: \(K_n^s\)

Name: A star
Definition: A graph of the form \(K_{1,n}\)
Page: 18
Chapter: 1
Section: 6

Q: [...] is [...].
A: The center of \(K_{1,n}\); the vertex in the singleton class
Page: 18
Chapter: 1
Section: 6
Variables: \(n>0\) and \(K_{1,n}\) a star.

Name: \(G\) is a subdivision of \(X\)
Definition: \(G\) is obtained when some edges are replaced by some pathes in \(X\).
Page: 19
Chapter: 1
Section: 7
Variables: \(X,G\) graphs
Name2: \(G\) is a \(TX\)(Topological \(X\))

Name: Branch vertices
Definition: The original vertices.
Page: 19
Chapter: 1
Section: 7
Variables: \(G\) a subdivision of \(X\)

Name: Branch sets of the \(IX\)
Definition: The sets \(V_x\).
Page: 19
Chapter: 1
Section: 7
Variables: \(X\) a graph and \(G\) a \(IX\)

Name: A contraction minor of \(G\)
Definition: The graph \(X\) which arises from \(G\) by contracting the subgraph \(V_x\).
Page: 19
Chapter: 1
Section: 7
Variables: \(X\) a graph
\(G\) a \(IX\) where vertices \(x\) are replaced by \(V_x\)

Q: Equivalently:
-[definition]
-[...].
-[...].
A: \(Y\) contains an \(IX\) as a subgraph; there is a partial map \(\phi:V(Y)\to V(X)\) such that for every vertex \(x\in X\), \(\phi^{-1}(x)\) is connected and for every edge \(xx'\in X\), there is an edge in \(Y\) between the branch sets \(\phi^{-1}(x)\) and \(\phi^{-1}(x')\); There is a sequence \(Y=G_0,\dots,G_n=X\) and each \(G_{i+1}\) arises from \(G_i\) by deleting an edge, contracting an edge or deleting a vertex
Page: 19, 20, 21
Chapter: 1
Section: 7
Variables: \(X,Y\) graphs
Name: \(X\) is a minor of \(Y\)/\(IX\) is a model of \(X\) in \(Y\)
Notation: \(X\preceq Y\)

Page: 20
Chapter: 1
Section: 7
Variables: \(X\) a graph and \(G\) an \(IX\).
Notation: \(P=\{V_x\mid x\in X\}\)
Typ: Partition of \(V(G)\)

Definition: \(G/P\) where \(P\) is the partition containing \(U\) and singletons.
Page: 20
Chapter: 1
Section: 7
Variables: \(G\) a graph and
\(U\subseteq V(G)\) connected.
Notation: \(G/U\)

Q: [...] [...] [IX and TX].
A: \(Y\) is a \(TX\); implies; \(Y\) is a \(IX\)
Page: 21
Chapter: 1
Section: 7
Variables: \(X,Y\) graphs.
Index: 3
Kind: Prop

\(\Delta(X)\le 3\) and \(Y\) is a \(IX\) implies \(Y\) contains a \(TX\).
Page: 21
Chapter: 1
Section: 7
Variables: \(X,Y\) graphs.
Index: 3
Kind: Prop

Name: An Euler tour
Definition: A tour which traverses every edge of the graph exactly once.
Page: 22
Chapter: 1
Section: 7
Variables: \(G\) a graph and \(w\) a closed walk

Name: Eulerian graph
Definition: A graph which admits an Eulerian tour.
Page: 22
Chapter: 1
Section: 7

Smaller0: \(G\) is Eulerian
Greater0: every edge of \(G\) has even degree
Page: 22
Chapter: 1
Section: 8
Variables: \(G\) a connected graph.
Kind: Theo
Smaller to greater: iff
Hide middle: yes

Name: The vertex space \(\mathcal V(G)\) of \(G\)
Definition: The vector space of all functions \(V\to\mathbb F_2\)
Page: 23
Chapter: 1
Section: 9
Variables: \(G=(V,E)\) a graph

Question: \(\mathcal V(G)\)'s dimension is
Answer: \(|V|\).
Page: 23
Chapter: 1
Section: 9
Variables: \(G=(V,E)\) a graph

Name: The standard basis of \(\mathcal V(G)\)
Definition: The set of functions sending exactly one vertex to \(1\).
Page: 23
Chapter: 1
Section: 9
Variables: \(G=(V,E)\) a graph

Definition: \(\sum_{e\in E}F(e)F'(e)\)
Page: 23
Chapter: 1
Section: 9
Variables: \(G=(V,E)\) a graph
\(F,F'\) in the edge space.
Notation: \(\langle F,F'\rangle\)

Name: The cycle span of \(G\)
Definition: spanned by all the cycles in \(G\).
Page: 24
Chapter: 1
Section: 9
Variables: \(G=(V,E)\) a graph
Notation: \(\mathcal C(G)\)
Index: , 1
Kind: , Prop
Definition2: a disjoint union of edge sets of cycles in \(G\)
Conjdef: Equivalently
Definition3: all vertex degrees of the graph \((V,D)\) are even
DefType: The set of graphs

Name: Cyclomatic number of \(G\)
Definition: The dimension of \(\mathcal C(G)\).
Page: 24
Chapter: 1
Section: 9
Variables: \(G=(V,E)\) a graph

Name: A cut in \(G\)
Definition: \(F\subseteq E\) such that \(F=E(V_1,V_2)\) for some partition \(\{V_1,V_2\}\) of \(V\).
Page: 24
Chapter: 1
Section: 9
Variables: \(G=(V,E)\) a graph

Name: The sides of \(F\)
Definition: The sets \(V_1,V_2\subseteq V\) such that \(F=E(V_1,V_2)\).
Page: 24
Chapter: 1
Section: 9
Variables: \(G=(V,E)\) a graph
\(F\) a cut

Name: A bond of \(G\)
Definition: A minimal non-empty cut in \(G\).
Page: 24
Chapter: 1
Section: 9
Variables: \(G=(V,E)\) a graph

Q: The cut for [...] is [...]
A: the partition \((\{v\},V\setminus\{v\})\); \(E(v)\)
Page: 24
Chapter: 1
Section: 9
Variables: \(G=(V,E)\) a graph
\(v\in V\)

Definition: The cut space of \(G\).
Page: 24
Chapter: 1
Section: 9
Variables: \(G=(V,E)\) a graph.
Notation: \(\mathcal B(G)\)
Index: 2
Kind: Prop

Q: [...]'s is generated by [...].
A: \(\mathcal B(G)\); \(E(v)\)
Page: 24
Chapter: 1
Section: 9
Variables: \(G=(V,E)\) a graph.
Index: 2
Kind: Prop

Smaller0: \(F\) is a bond
Greater0: the sides of \(F\) are connected
Page: 25
Chapter: 1
Section: 9
Variables: \(G=(V,E)\) a connected graph
\(F\) a cut
Smaller to greater: iff

Question: \(F\) can be represented as
Answer: a disjoint union of bonds.
Page: 25
Chapter: 1
Section: 9
Variables: \(G=(V,E)\) a connected graph
\(F\) a cut
Index: 3
Kind: Lem

Smaller0: \(\mathcal C(G)\)
Greater0: \(\mathcal B(G)\)
Page: 25
Chapter: 1
Section: 9
Variables: \(G=(V,E)\) a connected graph.
Index: 4
Kind: Theo
Smaller to greater: is the orthogonal complement of

Name: The fundamental cycle of \(e\)
Definition: The only cycle in \(T+e\).
Page: 26
Chapter: 1
Section: 9
Variables: \(G=(V,E)\) a connected graph
\(T\) a spanning tree and
\(e\in E\setminus E(T)\)
Notation: \(C_e\)

Name: The fundamental cut of \(f\)
Definition: The cut separating the two components of \(T\setminus f\).
Page: 26
Chapter: 1
Section: 9
Variables: \(G=(V,E)\) a connected graph
spanning tree \(T\)
\(f\in E(T)\)
Notation: \(C_f\)

Smaller0: \(f\in C_e\)
Greater0: \(e\in D_f\)
Page: 26
Chapter: 1
Section: 9
Variables: \(G=(V,E)\) a connected graph with spanning tree \(T\), \(e\in E\setminus E(T)\) and \(f\in E(T)\)
Smaller to greater: iff

Q: [...] is [property]
A: The fundamental cuts (cycles) of \(G\) with respect to \(T\); a basis of \(\mathcal B(G)\) (\(\mathcal C(G)\))
Page: 26
Chapter: 1
Section: 9
Variables: \(G=(V,E)\) a connected graph with spanning tree \(T\).
Index: 5 (i)
Kind: Theo

Question: The dimension of \(\mathcal B(G)\) is
Answer: \(|V|-1\)
Page: 26
Chapter: 1
Section: 9
Variables: \(G=(V,E)\) a connected graph
Index: 5 (ii)
Kind: Theo

Name: The incidence matrix, \(B\)
Definition: \(\left(\left\{\begin{array}{ll}1&\text{if }v\in e\\0&\text{otherwise}\end{array}\right.\right)_{v\in V,e\in E}\)
Page: 27
Chapter: 1
Section: 9
Variables: \(G=(V,E)\) a connected graph

Definition: The set of vertices adjacent to an even number of edges of \(F\).
Page: 27
Chapter: 1
Section: 9
Variables: \(G=(V,E)\) a connected graph,
\(F\subseteq E\)
Notation: \(B(F)\)

Question: \(B^t(U)\) is
Answer: the set of edges with exactly one end in \(U\).
Page: 27
Chapter: 1
Section: 9
Variables: \(G=(V,E)\) a connected graph
\(U\subseteq V\)
Context: Connected graph

Question: The kernel of \(B\) is
Answer: \(\mathcal C(G)\)
Page: 27
Chapter: 1
Section: 9
Variables: \(G=(V,E)\) a connected graph, let \(U\subseteq V\)
Index: 6
Kind: Prop

Question: The image of \(B^t\) is
Answer: \(\mathcal B(G)\)
Page: 27
Chapter: 1
Section: 9
Variables: \(G=(V,E)\) a connected graph
\(U\subseteq V\)
Index: 6
Kind: Prop

Name: Adjacency matrix, \(A\) of \(G=(V,E)\)
Definition: \(\left(\left\{\begin{array}{ll}1&\text{if }vv'\in E\\0&\text{otherwise}\end{array}\right.\right)_{v,v'\in V}\)
Page: 27
Chapter: 1
Section: 9
Variables: \(G=(V,E)\) a connected graph

Name: A down-set
Definition: A set \(X\subseteq V\) such that \(\lceil X\rceil =X\).
Page: 015
Chapter: 1
Section: 5
Variables: \(((V,E),r)\) a rooted tree
Name2: A set closed downward

Name: Subdivising vertices
Definition: The new vertices.
Page: 19
Chapter: 1
Section: 7
Variables: \(G\) a subdivision of \(X\)

Question: The dimension of \(\mathcal C(G)\) is
Answer: \(|E|-|V|+1\).
Page: 26
Chapter: 1
Section: 9
Variables: \(G=(V,E)\) a connected graph
Index: 5 (ii)
Kind: Theo

Definition: \((P,\{(X,Y)\mid \exists x\in X,y\in Y. (x,y)\in E(G)\})\)
Page: 20
Chapter: 1
Section: 7
Variables: \(G\) a graph and
\(P\) a partition of \(V(G)\), whose elements are connected
Notation: \(G/P\)

Name: The minimum degree of \(G\)
Page: 005
Section: 2
Variables: \(G=(V,E)\) be a non-empty graph.
Notation: \(\delta(G)\)

Question: There exists an enumeration \(v_1,\dots,v_n\) such that,
Answer: for all \(2\le i\le n\), \(v_i\) has a unique neighbor in \(\{v_1,\dots,v_i-1\}\).
Page: 014
Chapter: 1
Section: 5
Variables: \(T=(V,E)\) a tree with \(n\) vertices.
Index: 2
Kind: Corollary

Name: An inflated \(X\)
Definition: A graph \(G\), similar to \(X\), where some vertices \(x\) are replaced by disjoint connected graphs \(V_x\), and \((x,y)\) is replaced by a \(V_x-V_y\)-edge
Page: 19
Chapter: 1
Section: 7
Variables: \(X\) a graph
Abbreviation: An \(IX\)

Name: A bipartite graph
Definition: A graph which contains no odd cycle
Page: 18
Chapter: 1
Section: 6
Kind: Prop

Name: The \(k\)-th level of \(T\)
Definition: The set of vertices of height \(k\).
Page: 15
Chapter: 1
Section: 5
Variables: \(T=((V,E),r)\) a rooted tree
\(k\in \mathbb N\).