Complete Bipartite Graph: a graph that has its vertex set partitioned into two subsets of m and n vertices, respectively with an edge between two vertices if and only if one vertex is in the first subset and the other vertex is in the second subset.

• Denoted as k(m, n)

Subgraph - Graph G’(V’, E’) is a subgraph of G(V, E) if E’ is a subset of E and V’ is a subset of V, with each edge having the same end vertices as it does in G

A walk in the graph G:(V, E) is a finite seg of form v1, e_1, v_2, e_2, v_3, ... , e_k, v_k. The sequence alternates between vertices and edges, starting and ending with a vertex.

• Length of a walk = total number of edges in a walk that bring the initial vertex to the terminal vertex

• v1 is the initial vertex of the walk, vk is the terminal vertex of the walk

• Walk is said to be closed if terminal vertex = initial vertex

A trail is a walk with no repeated edges

A path is a walk with no repeted vertices and edges with exception of initial and end vertex

• A closed path is called a circuit; closed if initial vertex = terminal vertex

• A graph with no circuits is called circuitless

Theorem: A graph is circuitless when there are no loops and there is at most one path between any two given vertices

A walk starting at vertex u and ending at vertex v is called a u-v walk

• Two vertices u and v are connected if there is a u-v walk

In a circuitless graph, this implies that the distance between any two connected vertices is uniquely defined, which is a crucial property for tree structures.