Is there a graph $G$ containing a bridge-edge $e$, such that if you delete the edge $e$, the resulting graph $G-e$ is isomorphic to $G\times G$?
Such a graph, if it exists, would be a graph analogue of the golden ratio, which satisfies the equation $\varphi = \varphi^2-1$.
I've been thinking about the polynomial that characterizes the golden ratio: $\varphi^2 = \varphi + 1$. You can treat this as a matrix equation $\Phi^2 = \Phi + \mathbb{I}$ and find matrices that solve it, such as $\Phi = \begin{bmatrix}1&1\\ 1&0\end{bmatrix}$.
Now I wonder if it is possible to interpret this polynomial as an equation involving graphs. Graphs have direct sum and product, and as such we can take any polynomial $F(G) = \sum^n a_k G^k$ with non-negative integer coefficients $a_k$ and ask if it has a fixed point. Unfortunately, our polynomial involves a subtraction.
I wasn't sure what a natural definition of subtraction could be. In the category of graphs, there are sometimes things that behave like negative numbers (unlike in the category of sets), namely bridges. As far as connected components are concerned, if you add a bridge, you decrement the number of connected components. So provisionally, I take $G - 1$ to mean "G with exactly one additional bridge added" (though I'd accept an alternate definition if it's more natural).
This led to the current formulation of the question. So far, I've found:
- When you delete a bridge, the number of connected components increases by one. By assumption, this means that $G$ has one less component than $G-e \cong G\times G$. This means that $G\times G$ is disconnected, and therefore $G$ is.
- Furthermore, squaring a graph squares the number of components. Therefore, letting $c$ denote the number of connected components of $G$, the equation $G/e \cong G\times G$ forces $c+1 = c^2$. Among the real numbers, this equation is satisfied by the golden ratio. But $c$ is a cardinality; therefore, no finite solution can satisfy. It follows that $G$ must have infinitely many connected components.
- The universal property of the product might be useful? We have an inclusion $i:(G\times G - e) \hookrightarrow G\times G$, carrying the graph-without-bridge into the graph-with-bridge. And by assumption we have a graph isomorphism $q : G \cong (G\times G - e)$.
At this point, I become stuck trying to imagine a graph where you can delete a bridge and get something equivalent to $G\times G$. I've tried thinking about the individual components of $G$, but haven't been able to visualize something simple. Could you help me find a solution or prove that none exists?
I think this may work: let $N$ denote the edgeless graph with one vertex for every nonnegative integer. Let $E$ denote the graph consisting of two vertices joined by an edge. Then $E^k = E^{\boxtimes k} $ is the $k$-dimensional cube graph; formally let $E^0 $ be the graph consisting of a single vertex.
If we let $H$ be the disjoint union of all the $E^k$: $$H\equiv E^0 + E^1 + E^2 + E^3 + \ldots$$ Then define $$G\equiv N \times H.$$
We have that $G$ consists of countably infinite disjoint copies of each $E^n$. (You can visualize this as a lattice of nonnegative numbers, where at each $(m,n)$ there is another disjoint copy of $E^n$.)
Now, because all the amounts involved are countably infinite, $G\times G$ also contains countably infinitely many copies of each $E^n$, and will still contain countably infinitely many copies of each, even if we delete an edge, transforming one copy of $E^1$ into two copies of $E^0$.
Therefore there is an isomorphism carrying $G\times G$ to $(G-e)$; for each $n$, we bijectively map the countably infinitely many copies of $E^n$ in $G\times G$ onto the countably infinitely many copies of $E^n$ in $(G-e)$.
So I've gotten an answer, but this makes me feel like I formulated the original question and the ~categorization of $\phi$ wrongly --- $G= N\times H$ certainly satisfies the equation as I defined it, but then again I think $G$ also satisfies every other polynomial equation over the nonnegative integers in $G$, so it's not especially satisfying.