Created at:

Modified at:

# Preliminary definitions for sets

subset
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

# Notation

G
case letters are used to represent a graph.
V(G)
vertices of graph G.
E(G)
edges of graph G.
G[S]
subgraph of G induced by set of vertices S. Alternative notation: <<S>>_G
G[X]
TODO

# Definitions

These are definition taken from book A First Course in Graph Theory, by Gary Chartrand and Ping Zhang.

graph
TODO
vertex
TODO
edge
TODO
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]
"Distinct edges incident with a common vertex are adjacent edges". [1.2]
subgraph
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]
walk
"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]
trail
A u -- v trail is a u -- v walk in which no edge is traversed more than once. [1.2]. (Portuguese: "trilha").
path
A u -- v path is a u -- v walk in which no vertex is repeated. [1.2]. (Portuguese: "caminho").
circuit
"A circuit in a graph G is a closed trail of length 3 or more." [1.2]
cycle
"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]
distance
The length of the path between two connected vertices. [1.2]
geodesic
The shortest path between two vertices, if they are connected. [1.2]
diameter
The greatest distance between two vertices of a connected graph. [1.2]

# References

A First Course in Graph Theory, by Gary Chartrand and Ping Zhang