Graph Theory part 2 – Structural Properties

Last week, I did an overview about graph theory, including two types of graphs: directed and undirected graphs. This time, I would like to dig further into some other forms that would define graphs more specifically than just the two overarching types above. Let’s see some of the structural properties of graphs for a more in-depth look.

1. Connectivity:

The connectivity of a graph is decided by whether each pair of nodes in the graph are linked (i.e. there is a way to go between them, disregarding the direction of the edges in the cases or not). 

In the case of an undirected graph, if for every pair of nodes A and B there is a link between them, then it is connected.

In the case of a directed graph, things are a little bit more complicated, since you have to take into account the direction of the edges. There are, therefore, three levels of connectivity:

• A strongly connected graph means that for every pair of nodes A and B, there is a way to go from A to B and a way to go from B to A. 

• A weakly connected graph is a graph that would become connected if the directions of the edges are disregarded. In other words, there is at least one pair of nodes A and B that has no path between them, due to the arrows not following the intended way.

• A unilaterally connected graph has at least a one-way link between every pair of nodes. So there exists at least a pair of nodes A and B that is not connected two-way, or else the graph would change to be strongly connected.

So, the levels of connectivity can be ranked as: 

Strongly connected > Unilaterally connected > Weakly connected

2. Walk, Trail, Path, Cycle, and Circuit:

Why do those words sound kind of like synonyms?

Err, yes, but not in graph theory. They do have a similarity, however: All five of them are sequences of points and edges between those points. And that is pretty much it.

• A walk is a sequence of vertices and edges. They can repeat, and they need not be closed. In the figure above, ABCEFCEC is a walk.

• A trail is a walk that does not repeat edges. ABCE is a trail. ABCEA is a trail. ABCEC is not a trail. All trails are walks, but not the reverse.

• A path is a trail but does not repeat vertices. So ABCE is a path, but ABCEA is not. All paths are trails and walks.

• A cycle is a closed trail with no repeating vertices except for the beginning and the ending vertices. For example, ABCEA is a cycle.

• A circuit is just a closed trail, so its vertices can repeat. For example, CFEDAEC is a circuit. All cycles are circuits.

3. Complementary graphs:

The complementary graph of a graph G is the graph G^C  such that every connection missing in G is in G^C but the two graphs have no common connection. Therefore, merging the two graphs together will create the complete graph. As demonstrated in the figure above, complementary graphs allow for two-way edges and self-loops (i.e. an edge with the same vertex as beginning and ending).

To construct the complementary graph of a graph, the method is to list down and then connect all the missing edges, and in the case of a directed graph, all the missing directions of existing edges as well.