graph theory
I read a lemma.
$J$ is the all ones $n \times n$ matrix, $I_n$ is the $n \times n$ identity matrix. Let the adjacency matrix of a simple graph $G$ on $n$ vertices be $A = A(G)$. Then the adjacency matrix of its complement is $\bar A = A \bar{(G)} = J – I – A$.
From a previous posting, I know that $\bar A=J-I-A$. Can anyone help me understand how? The linked question has no comments regarding this.
The dual of a planar graph depends on how it is embedded in the plane: "The same planar graph can have non-isomorphic dual graphs." (See Wikipedia illustration.)
Although this graph is not regular, it can be modified to obtain a cubic (3-regular) graph with more than one planar embedding and associated nonisomorphic dual graphs. Replace the left- and right-hand vertices of degree two in the top diagram with a "diamond" subgraph, connecting to its top and bottom nodes to produce all nodes of degree 3:
Now the outer face of the top graph will have its maximum degree 10, but the corresponding replacement in the alternative embedding yields a maximum degree 7 (shared by the outer face and one inner face). So the dual (multi-)graph depends on the embedding and cannot be inferred only from the adjacency matrix of the original graph.
So I'd say in the general sense you've asked, it cannot be done without pencil-and-paper or some other visualization of the embedding.
It is a directed graph, i.e. \begin{equation} \begin{matrix} a & & b\\ \updownarrow & X & \uparrow\\ c &\leftrightarrow & d \end{matrix} \end{equation}
where I used $X$ to denote a double-sided link between $a$-$d$ and $c$-$d$.
The direction of the edges is convention defined and could be reversed.
Best Answer
You want to prove that if the adjacency matrix of the graph $G$ is $A$, then the adjacency matrix $\overline{A}$ of the complement graph $\overline{G}$ is $J-I-A$. Observe that vertices $i$ and $j$ are adjacent in $G$ iff vertices $i$ and $j$ are nonadjacent in $\overline{G}$. Hence, the edge set of $G$ and of $\overline{G}$ together form the edge set of the complete graph $K_n$. Observe that the adjacency matrix of the complete graph is $J-I$. Hence, $A + \overline{A} = J-I$. So, $\overline{A} = J-I-A$.