This graph has 1 edge and 5 nodes.

There can exist another graph for facebook – it is possible to have a facebook where no one is friends with each other. In this case, there are no edges: we have an edgeless graph.

However, we say that if there is not at least one account on facebook, there is no facebook. There can be no graph with less than 1 nodes.

The degree of a node is the facebook friend count of the node. If A has exactly 1 friend, the degree of A must be exactly 1. Since A’s friend must also be on facebook, there is an important implication we made: there must be exactly 1 account on facebook with degree at least 1.

In our case, this account is E, and E happens to have exactly 1 facebook friend too – the friend is A. We represent these as:

deg(E) = 1, deg(A) = 1

Now let us say for a second that E has degree 2. What does this imply?

That there is another node – B, C, or D – which is friends with E.

In fact, for every added degree to a node n, there must be another node q that must have exactly 1 more degree. q cannot already have an edge with n, since there can only exist one edge (friendship) between q and n (they can’t be facebook friends twice at the same time).

Using this principle, we can understand the Handshaking Lemma. First, let’s say we have a total of e edges and v nodes in our graph. Then:

2*e = \sum_{i=1}^{v} deg(n_i)

The left hand side is 2*e. The right hand side is adding up the individual degrees (facebook friend numbers) of each of our nodes, from node 1 (since we must have at least 1 node in a graph) to node v. For the graph in Fig 1:

e = 1, v = 5, n_1 = A, n_2 = B, n_3 = C, n_4 = D, n_5 = E.

2*1 = deg(A) + deg(B) + deg(C) + deg(D) + deg(E) = 1+0+0+0+1 = 2.

This makes sense – if E is facebook friends with A, then both have 1 facebook friend on their friend list, and have exactly one friendship between each other.

A directed graph would be one where an edge goes from one node to another. For instance, on instagram: A could follow E (A \rightarrow E), but that would not imply that E follows A.

Facebook is an undirected graph: A \rightarrow E \iff E \rightarrow.

Therefore, the graph is also a “simple graph”. This is because we do not consider 2 (or more than 1) edges between 2 nodes, and a node cannot make a node to itself (these ideas work in directed graphs). This makes it simple.

When we described the graph in Figure 1, we used 2 independent variables without even thinking about it: the number of nodes, and the number of edges. The number of degrees are another variable, however it is not independent.

The (undirected) graph G for this graph is defined as:

G = (V, E)

V is formally defined as a nonempty (|V| \geq 1) set of nodes. E is formally defined as:

E \subset 2^{V}; E = {e \in 2^{V} | |e| = 2}

In Fig 1:

V = {A,B,C,D,E}, |V| = 5

2^V = {{},{A},{B},{C},{D},{E},{A,B},{A,C},{A,D},{A,E},{B,C},{B,D},{B,E},{C,D},{C,E},{D,E},{A,B,C},{A,B,D},{A,B,E},{A,C,D},{A,C,E},{A,D,E},{B,C,D},{B,C,E},{B,D,E},{C,D,E},{A,B,C,D},{A,B,C,E},{A,B,D,E},{A,C,D,E},{B,C,D,E},{A,B,C,D,E}}

Since an edge can exist between exactly 2 unique nodes, we consider the following from the powerset: {{A,B},{A,C},{A,D},{A,E},{B,C},{B,D},{B,E},{C,D},{C,E},{D,E}}

In Fig 1, we have an edge A-E. Therefore E = {{A,E}} or {A-E}. (We can use – formally to show an edge)

We can calculate the degree of each node by counting the number edges incident to it, and the cardinality of the set of degrees using the Handshaking Lemma:

2*|E| = \sum_{v \in V}^{} deg(v)

From this, it follows that there must be an even number of odd-degree nodes (link).

The undirected graph we just considered is the same as an undirected graph in graph theory in higher mathematics. Welcome to graph theory.