Notes on Graph Theory
Preliminary definitions for sets
- `A subset B`. "Set A is said to be a subset of Set B if all the elements of Set A are also present in Set B. In other words, set A is containted inside Set B." " A subset can be equal to the set."
- proper subset
- `A subseteq B`. "Set A is considered to be aproper subset of Set B if Set B contains at least one element that is not present in Set A.". `A subset B, A != B`
Definitions (quoted part) taken from:
Subsets- Definition, Symbol, Proper and Improper Subset | Power Set
- case letters are used to represent a graph.
- vertices of graph `G`.
- edges of graph `G`.
- subgraph of `G` induced by set of vertices `S`. Alternative notation: `<<S>>_G`
These are definition taken from book A First Course in Graph Theory, by Gary Chartrand and Ping Zhang.
- adjacent vertices
- Given two vertices, `u` and `v`, "If `uv` is an edge in `G`, then `u` and `v` are said to be adjacent in `G`." [1.1] (a.k.a. neighbors [1.2])
- order of a graph
- Number of vertices in the graph. [1.1]
- size of a graph
- Number of edges in the graph. [1.1]
- incident vertex and edge
- if a vertex `v` is connected to an edge `e`, then vertex `v` and edge `e` "are said to be indicent with each other". [1.2]
- adjacent edges
- "Distinct edges incident with a common vertex are adjacent edges". [1.2]
- A graph H is called a subgraph of a graph G if H contains a subset of vertices and edges of G. `H subseteq G`, if `V(H) subseteq V(G)` and `E(H) subseteq E(G)`. [1.2]
- proper subgraph
- "If `H subseteq G` and either `V(H)` is a proper subset of `V(G)` or `E(H)` is a proper subset of `E(G)`, then `H` is a proper subgraph of G."
- induced subgraph
- Given a graph `G`, a graph `F` is an induced subgraph of a graph `G` if, for every vertex pair `u,v` common to both `G` and `F`, every edge `uv` that exists in `G`, also exists in `F`. In other words: "A subgraph `F` of a graph `G` is called an induced subgraph of `G` if whenever `u` and `v` are vertices of `F` and `uv` is an edge of G, then `uv` is an edge of F as well." "If `S` is a nonempty set of vertices of a graph `G`, then the subgraph of `G` induced by `S` is the induced subgraph with vertex set S. This induced subgraph is denoted by `G[S]`." [1.2]
- edge-induced subgraph
- Given a graph `G` and a subset of its edges `X`, the subgraph `G[X]` "consists of all vertices that are incident with at least one edge in `X`." [1.2]
- "A `u` -- `v` walk walk in `G` is a sequencie of vertices in `G` beginning with `u` and ending at `v`." [1.2]. (Portuguese: "passeio").
- closed walk
- A closed walk is a `u` -- `v` walk where `u = v`. [1.2]
- open walk
- A open walk is a `u` -- `v` walk in which `u != v`. [1.2]
- length of a walk
- Number of edges in a walk. [1.2]
- A `u` -- `v` trail is a `u` -- `v` walk in which no edge is traversed more than once. [1.2]. (Portuguese: "trilha").
- A `u` -- `v` path is a `u` -- `v` walk in which no vertex is repeated. [1.2]. (Portuguese: "caminho").
- "A circuit in a graph G is a closed trail of length 3 or more." [1.2]
- "A circuit that repeats no vertex, except for the first and last, is a cycle. A k-cycle is a cycle of length `k`. A 3-cycle is also referred to as a triangle." [1.2]
- connected vertices
- "saying that `u` and `v` are connected only means that there is some `u` -- `v` path in `G`; it doesn't say that `u` and `v` are joined by an edge." [1.2]
- connected graph
- "A graph `G` is connected if every two vertices of `G` are connected" [1.2]
- disconnected graph
- A graph that is not connected. [1.2]
- The length of the path between two connected vertices. [1.2]
- The shortest path between two vertices, if they are connected. [1.2]
- The greatest distance between two vertices of a connected graph. [1.2]
A First Course in Graph Theory, by Gary Chartrand and Ping Zhang