Representing Graphs as Bit Strings:

Before we begin we need a way to represent a graph as a bit string, and graph properties as Boolean functions on that bit string if we wish to apply Theorem or any of its derivatives. When representing graphs as bit strings it is helpful to restrict the types of graphs we will consider.

A simple graph has no multiple edges or loops. The adjacency matrix $A$ of a simple directed graph has $a_{ij} = 1$ if and only if there is a directed edge from vertex $i$ to vertex $j$. Since $a_{ii} = 0$ for all vertices $i$ of a simple graph, we need only $V(V-1)$ bits to represent such graphs with $V$ vertices. For undirected graphs, the adjacency matrix is symmetric across the diagonal. Thus we can represent any undirected simple graph with a bit string of length $V(V-1)/2$. A simple undirected graph is depicted in Figure , its above-diagonal adjacency matrix representation can be seen in Table . Now that we can represent a graph by its above diagonal adjacency matrix, graph properties are simply Boolean functions on matrix representations.

Figure: An Undirected Graph

Table: Above Diagonal Adjacency Matrix Representation of the Graph in Figure