What is Simple Graph?
As opposed to a multigraph, a simple graph is an undirected graph that has no loops (edges connected at both ends to the same vertex) and no more than one edge between any two different vertices. In a simple graph the edges of the graph form a set (rather than a multiset) and each edges is a distinct pair of vertices. In a simple graph with n vertices every vertex has a degree that is less than n (the converse, however, is not true - there exist non-simple graphs with n vertices in which every vertex has a degree smaller than n).
What is Regular Graph?
Regular Graph: A regular graph is a graph where each vertex has the same number of neighbours, i.e., every vertex has the same degree or valency. A regular graph with vertices of degree k is called a k-regular graph or regular graph of degree k.
What is Complete Graph?
Complete Graph: Complete graphs have the feature that each pair of vertices has an edge connecting them.A complete graph with 5 vertices. Each vertex has an edge to every other vertex.
Prove that a complete graph is a also a regular graph.
Let Graph G is a complete graph, and assume its contains n vertices. Because it is a complete graph, so there exists an edge between every 2 vertices, in other words, for vertex vi, it connects to (n-1) other vertices. So its degree is (n-1).
For i = 1, 2, ..., n, degree(vi) = n - 1. So Graph G is also a regular graph with (n-1) degrees.
What is a Path?
In graph theory, a path in a graph is a sequence of edges which connect a sequence of vertices. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex. Both of them are called terminal vertices of the path. The other vertices in the path are internal vertices.
What is a Cycle?
A cycle is a path such that the start vertex and end vertex are the same. The choice of the start vertex in a cycle is arbitrary.
What is forest?
A forest is a graph with no cycles (i.e. the disjoint union of one or more trees).
What is tree?
A tree is a connected graph with no cycles.
Please explain: If for each vertex, there exist paths to other vertices, then this graph is connected.
In an undirected graph G, two vertices u and v are called connected if G contains a path from u to v. Otherwise, they are called disconnected. A graph is called connected if every pair of distinct vertices in the graph is connected, otherwise, it is called disconnected.
If for each vertex, there exists a path it to aother vertex, then we can also say that if I chose 2 distinct vertices u and v arbitrarily from Graph G, there exists at least one path from u to v, in other words, that the u and v are connected. Because the u and v are chosen arbitrarily, so every other distinct pair of vertices in the graph is connected, and so the graph G is connected.