**Graph**: Nodes (vertices) and edges.**Isolated**: a node without an incident edge.

**Empty**graph: no vertex.**Multi**-graph: 2 or more edges on the same pair of vertices.**Simple**graph: no loop, no parallel edges.**Directed**graph (digraph): each edge is represented by an ordered pair (directions of edges matter).**Complete**graph: simple; every vertex connected to every other distinct vertex.**Bipartite**graph: vertices can be partitioned into 2 disjoint subsets.**Complete Bipartite**graph: each node has an edge to every node in the other subset.**Sub**-graph: node and edge sets are subsets of a graph.

- Degree of a
**vertex**: number of edges incident on this vertex; loops are counted twice. - Total Degree of a graph:

(from

**Walk**: a finite alternating sequence of adjacent vertices and edges.**Path**: a walk with no repeated edge.**Simple**: a path with no repeated vertex other than the possibility that. **Closed**: a walk that starts and ends at the same vertex.**Circuit**: a closed path.**Cycle**: a simple circuit.**Trivial Circuit**: only one vertex, no edge.

- Connected (for
**two vertices**): there exists some walk in between. - Connected (for a
**graph**): every two vertices are connected. - If
is a Connected Component of : is a sub-graph of . is connected. is not a proper sub-graph of any connected sub-graph of .

- Out-degree

- In-degree

A closed walk of a graph

- Non-repeated edges forming a subset of
. - Non-repeated vertices, except the same start/end vertex, forming the full set of
.

From

A path that starts at

A closed walk of a graph

- Non-repeated edges forming the full set
- Possibly repeated vertices forming the full set

- Tree: a connected graph only containing trivial circuits.
**Acyclic Direct Graph**: a directed graph without a non-trivial directed cycle.**Leaf**(Terminal Vertex) of a tree with 2 or more vertices: a vertex of degree 1.

A graph

- The total degree of a graph equals twice the number of edges.
- In any graph, the number of vertices of odd degree is even.
- If
, are vertices on a circuit in , then if one edge is removed from this circuit, there still exists a path in between. - If
is connected and contains a circuit, then an edge of the circuit can be removed without disconnecting . - An Euler path from
to exists ⇔ is connected, and have odd degree, and all other vertices of have even degree. - A graph
contains an Euler circuit ⇔ is connected, and every vertex of has even degree. - If
is a connected graph with vertices, , such that for any pair of nonadjacent vertices and in , then has a Hamilton circuit. - Any tree that has
vertex has at least one vertex of degree . - Any tree of
vertices has edges. - If a connected graph has
vertices and edges, it is a tree. - If a graph
contains a Hamiltonian circuit, then must contain a sub-graph that: - Is connected.

View / Make Comments