In this lesson, we'll review the main definitions used in graph theory.

Basically, the goal of this lesson is to make sense of the following sentence.

An isolated vertex forms a component.

Don't worry of this sentence seems ridiculous to you.

By the end of this lesson,

we'll see what it means in Graph Theory.

The first definitions is the degree of a vertex.

In the Facebook graph for example,

the degree of some vertex is just the number of its friends.

We're going to define it formally.

The degree of a vertex is the number of its incident edges.

Or in other words, it's the number of its neighbors.

We denote the degree of a vertex v by deg of v. And also we'll

say that the degree of a graph or the maximum degree of

a graph is the maximum degree of its vertices.

Let's see some examples.

The degree of vertex v in this example is six.

It is connected to six other vertices.

And the degree of the vertex v six is one,

because it's only connected to v. In a cycle,

every vertex has degree two,

because it's connected to the previous vertex and to the next one.

Let us see one more example.

In this graph, this is one graph.

In this graph, the degree of the vertex v2 is exactly two.

The degree of the vertex v8 is one.

But the degree of vertex v zero is zero.

This vertex is not connected to anything.

It's not incident of any edge.

Such a vertex is called an "isolated vertex.

"Again, a vertex of degree zero is called an "isolated vertex."

A graph is called a regular if all vertices has the same degree.

For example, in this graph,

the degree of every single vertex is same.

So, this graph is a regular.

Also, if the degree of every vertex of a graph is k, we call it "k-regular."

So, we're going to call this graph "3-regular."

Okay. If some graph G, then the complement of this graph

which is usually denote by G bar,

the graph with the same set of vertices as G,

which contains an edge,

if and only if G doesn't contain this edge.

So, the complement of G contains all edges,

which do not belong to G. In other words,

the edge U V belongs to the graph G bar or the complement of G,

if and only if the edge U V does not belong to the original graph G. Here's an example.

On the left, you see some graph G and on the right, you see its complement.

For example, the original graph,

the vertex v1 is connected to v2, v3 and v4.

Its complement is connected to the other vertices,

that would be v5 and v6.

Similarly, v3 in the original graph is connected to all vertices, but v5.

And this is why in G complement,

v3 is connected to only v5.