Simple Graphs
Drag nodes to rearrange the graph. Add a new node by double clicking the plane.
Click a node to select. Clicking another node will draw a new edge, clicking the same node will remove it and any incident edges. Click the background to unselect a node.
Double click an edge to remove it.
Hover over a node to view its distance from all other nodes.



Show Label   Show Degree
Color Components
Display Matrix:

Order (number of nodes):
Size (number of edges):
Degree vector: [ 3, 3, 3, 3 ]
Components: Yes
Regular: Yes
Eulerian: Yes
Spanning Trees: 2
About Simple Graphs
A simple graph is an undirected graph with no loops or multiple (parallel) edges.

Matrices
The adjacency matrix \(A\) of a simple graph on \(n\) nodes will be an \(n\times n\) real, symmetric matrix. The \(i\)th row and \(i\) column of the matrix is associated with node \(n_i\). The \((i,j)\)th entry of the matrix will be a 1 if nodes \(n_i\) and \(n_j\) are adjacent (connected by a single edge) and a 0 otherwise. Since simple graphs do not include loops, the diagonal entries of this matrix will always be 0.

The degree matrix \(D\) of a simple graph on \(n\) nodes will be an \(n\times n\) diagonal matrix. The \((i,i)\)th entry of this matrix will be the degree of node \(n_i\).

The Laplacian matrix \(L\) of a simple graph on \(n\) nodes will be an \(n\times n\) symmetric matrix. It is defined as the difference between the the degree and adjacency matrices, \(L = D-A\). The eigenvalues of this matrix have particular importance, and can be used to determine information about the connectedness of the graph. By Kirchoff's theorem, we can determine the number of spanning trees in the graph using these eigenvalues as well.

Connected Components
A connected component in a simple graph is a maximal subset of mutually connected nodes and the edges between them. Mutually connected means we can find a path from any node in the component to any other node in the component. Every node in the graph belongs to exactly one connected component, with isolated nodes each forming their own component. The graph is called connected if it has only one connected component.

Breadth first search (BFS) and depth first search (DFS) are common algorithms to find connected components (and determine if the graph is connected).

We can find the number of connected components will be equal to the dimension of the nullspace (kernel) of the \(n \times n\) laplacian matrix. The rank \(r\)of this matrix will be equal to the number of its non-zero eigenvalues, and so the number of connected components can be found by \(n-r\). This is the method used to find the number of components in this applet. Note that rounding error in the calculation of eigenvalues may occasionally case an error in this calculation, particularly for large numbers of nodes.

Eulerian Paths and Cycles
An Eulerian cycle traverses every edge of the graph exactly once, beginning and ending with the same node. A graph with a single connected component, or one non-trivial component and isolated nodes, has an Eulerian cycle if and only if every node has even degree. If such a graph instead has exactly two nodes with odd degree, then the graph will have an Eulerian path. This is a walk that traverses every edge exactly once, but begins and ends at different nodes. The path will always begin with one of the nodes of odd degree, and end at the other.
Using the Applet
You can construct any simple, undirected graph using this applet and find some information about the graph and its vertices.

Double click on the background area to create a new node. Click one node, followed by another, to add a new edge (multiple edges between the same pair of nodes will be ignored). Double click an edge or node to remove it.

If you hover your mouse pointer over a node, the distance from that node to all other nodes will be displayed. An empty distance means that the node is not reachable from the selected node.

As you make changes to the graph, its statistics and matrices will automatically update. You can choose which matrix to display, if any.
About the Applet
This applet was created using JavaScript, the Konva.js graphics library, and the Math.js mathematics library.