Assume that $G$ is connected. Now, if $G\sim(G')'$, consider the maximum clique, on vertices $\{v_1,\ldots, v_n\}$ of $G$. If we have a vertex $v$ connected to the clique, WLOG at $v_1$, and $n\ge 3$, then $G'$ contains all edges $vv_i$ for $i\neq 1$. In particular, it has $vv_2$ and $vv_3$, so $(G')'$ contains all edges $vv_i\forall i\neq 2$ and $vv_i\forall i\neq 3$. So, $v$ is connected to all vertices $\{v_i\}$ in $(G')'$, and $\{v,v_1,\ldots, v_n\}$ form a $K_{n+1}$, which is a contradiction to maximality. Thus, either $n\ge 3$ and $v$ does not exist, or $n=2$. In the former, we have that $G$ must be a clique, as it is connected. In the latter, we have that $G$ has no triangles. However, if a vertex $v$ is connected to $v_1,v_2,v_3$, then $G'$ and $(G')'$ contain triangle $v_1v_2v_3$, which is a contradiction to $G\sim(G')'$. Thus, no vertex with 3 neighbors exists, and we have that $G$ is either a cycle or a path. If $G$ is an even cycle or a path, then $(G')'$ is disconnected, which is a contradiction. So, $G$ is an odd cycle. Hence, if $G$ is connected, it is a clique or odd cycle. To finish, suppose that $G$ is composed of a number of connected components. If we consider the one, $H$, with the maximum clique (suppose that $G$ has a triangle), note that if $G\sim (G')'$, it must map to itself, so it is a clique, and $H=H'=(H')'$. Thus, we can just remove it from $G$. Continue this until $G$ is triangle free. From above logic, it must be composed of cycles and paths. However, if it has an even cycle or a path of size $>2$, then $(G')'$ has more connected components, which is a contradiction. So, it is composed of isolated vertices, edges, and odd cycles, which all are fixed under $'$, and hence $G$ is as well.

william122 wrote: As the $'$ operation acts independently on connected components, WLOG that $G$ is connected. This first step is not valid, because it could be the case that $G \cong G_1 \sqcup G_2$ and yet $G_1' \cong G_2$, $G_2' \cong G_1$, say. (But it's easy to fix.)

william122 wrote: As the $'$ operation acts independently on connected components, WLOG that $G$ is connected. Now, if $G\sim(G')'$, consider the maximum clique, on vertices $\{v_1,\ldots, v_n\}$ of $G$. If we have a vertex $v$ connected to the clique, WLOG at $v_1$, and $n\ge 3$, then $G'$ contains all edges $vv_i$ for $i\neq 1$. In particular, it has $vv_2$ and $vv_3$, so $(G')'$ contains all edges $vv_i\forall i\neq 2$ and $vv_i\forall i\neq 3$. So, $v$ is connected to all vertices $\{v_i\}$ in $(G')'$, and $\{v,v_1,\ldots, v_n\}$ form a $K_{n+1}$, which is a contradiction to maximality. Thus, either $n\ge 3$ and $v$ does not exist, or $n=2$. In the former, we have that $G$ must be a clique, as it is connected. Clearly, this implies $G\sim G'$. In the latter, we have that $G$ has no triangles. However, if a vertex $v$ is connected to $v_1,v_2,v_3$, then $G'$ and $(G')'$ contain triangle $v_1v_2v_3$, which is a contradiction to $G\sim(G')'$. Thus, no vertex with 3 neighbors exists, and we have that $G$ is either a cycle or a path. If $G$ is an even cycle or a path, then $(G')'$ is disconnected, which is a contradiction. However, if $G$ is an odd cycle, then it is clear that $G'$ is isomorphic to $G$, as desired. As we have exhausted all cases, we are done. I think this proof has a slight hole. Technically the operation could swap connected components, so we can't exactly WLOG $G$ connected. edit: sniped

Replace $G'$ with $f(G)$. Call an operation $f$ leeking. We will prove the following stronger claim. Claim: If $G$ is connected and $f^n(G)\cong G$ for some $n$, then $G$ must be either a clique or an odd cycle. Proof: Note that after leeking, each triangle must be preserved. Therefore the number of triangles must be non-decreasing. Since after leeking $n$ times, the number of triangles are the same, this means leeking $G$ must never form a new triangle. We will split into two cases. Case 1: $G$ has a triangle. Then take a maximal clique $K = \{x_1,x_2,\hdots,x_n\}$. Suppose that there exists a vertex $a\in G\setminus K$. Then since $G$ is connected, there exists a vertex in $K$ that is adjacent to $a$, say $x_1$. Since $K$ is maximal, there exists $i$ such that $ax_i$ is not an edge. However, this means leeking $G$ forms a new triangle $ax_ix_j$ (which all have common neighbour $x_1$) for any $j$, contradiction. Hence $G$ must be a clique. Case 2: $G$ has no triangles. Then any vertex of $G$ has degree at most two; if there exists vertices $a,b,c,d$ which $a$ is adjacent to $bcd$, then leeking $G$ forms triangle $bcd$, contradiction. This forces $G$ to be a tree of a cycle. If $G$ is a cycle, then clearly even cycle fails so we are done. If $G$ is a tree, it's easy to prove that any tree which each vertex has degree at most two must be a path (induct and remove any leaf). Thus $G$ must be a path $x_1x_2\hdots x_n$. But then leeking $G$ disconnects the graph, which gives a contradiction. $\blacksquare$ Back to the main problem, label each connected component of $G$ as $1,2,\hdots,n$. Suppose that $f(f(G))$ turns the $i$-th component to $\sigma(i)$. Since permutations can be written in cycles, there exists large $N$ such that $\sigma^N$ is identity. This means the $i$-th connected component of $f^{2N}(G)$ is isomorphic to the $i$-th connected component of $G$. Applying the claim, we find that each connected component must be a clique of an odd cycle. Hence we are done.

So this is my problem (along with Zack Chroman.) An interesting (and much harder) variant is if one defines $G_\ell = G_{\ell-1}'$ then the operation stabilizes in 100$\log(|V(G)|)$ steps.

mssmath wrote: So this is my problem (along with Zack Chroman.) An interesting (and much harder) variant is if one defines $G_\ell = G_{\ell-1}'$ then the operation stabilizes in 100$\log(|V(G)|)$ steps. hmm it seems none of the standard solutions can adapt to this, since they seem to give an $O(|V|)$ bound...

We need to show that all connected components are either odd cycles or cliques. This will complete the proof.

So my solution was the following (it immediately hints how to get the $\log(|V(G)|)$ type bound mentioned. However I leave these details to an interest readers. The key claim is that after a finite number of steps of the process $G_{\ell+1} = G_{\ell}'$ that the graph is a union of odd cycles and complete graphs. To prove this note that eventually the graph as all components being either of size $1$ or being non-bipartite. Then fix a non-bipartite component. If it an odd cycle we are done. Else fix an odd cycle and note that the vertices on this cycle always still form a cycle. Now note for any vertex not on this cycle the distance to the cycle essentially halves. Thus we reduce to a case where we have an odd cycle and essentially a set of vertices distance $1$ away from the cycle and these are trivial to show becoming a complete graph.

Beautiful graph! Let's start with the following observations. In the following solution, we assume the original graph to be connected. Otherwise, just consider each of its component. Warming Up. If $A$ and $B$ are disconnected graph, then $A'$ and $B'$ are disconnected as well. Proof. Suppose $A'$ and $B'$ are connected, then there exists a vertex $a \in A'$, $b \in B'$ such that $a - v - b$ is connected initially, a contradiction. Lemma 01. The number of triangles after each operation $G \to G'$ is non decreasing. Proof. Consider any triangle in the graph. Let it be $A - B, B - C, C - A$. Notice that every two of them has a common neighbor, which is the third one. Therefore, the edges will be preserved under the operation $G \to G'$. Hence, any triangle in the original graph $G$ will be preserved in graph $G'$ as well. Now, notice that since $G$ and $(G')'$ are isomorphic, this means that the number of triangles in each graph are the same. By Lemma 01, since the number of triangles under the process $G \to G' \to (G')'$ is non decreasing. Then, we know that the number of triangles in $G$ and $G'$ is the same as well. SubLemma. Let $H$ be a subgraph of $G$, then $H$ and $H'$ need to have the same number of triangles. Proof. By Lemma 01, the number of triangles in $H'$ is at least as many as the number of triangles in $H$. Now, suppose that the number of triangles in $H'$ is more than the number of triangles in $H$. Since $H$ is a subgraph of $G$, and $H'$ is a subgraph of $G'$, then we have that the number of triangles of $G'$ is greater than the number of triangles in $G$, a contradiction. Lemma 02. If any vertex $v$ of graph $G$ has degree greater than or equal to 3, than the subgraph containing vertex $v$ and its neighbors must be a complete graph. Proof. Consider any vertex $v$ which has degree greater than or equal to $3$. Name the subgraph as $H$. Now notice that $H$ contains a vertex $v$ such that for any two non-$v$ distinct vertices $u$ and $w$, then $u$ and $w$ have a common neighbor $v$. Therefore, all $(u,v)$ must be connected. Now, notice that this contributed at least $\binom{n}{2}$ triangles to the new graph - all of which are without vertex $v$. Since we need $H$ and $H'$ to have the same number of triangles, we need the original graph to have at least $\binom{n}{2}$ triangles as well. Notice that if we add any edge $(u,w)$ to graph $G$ such that the new triangle formed has vertex $v$, then it will add $1$ triangles both on $G$ and $G'$ since the number of triangles of $G$ increase by $1$ and number of triangles of $G'$ increase by at least $1$ as well. Therefore, the triangle that can actually decrease the number of triangles in both graph is the triangle formed without vertex $v$. Using this reasoning, one can eventually prove that graph $H$ has to contain all the edges $(u,w)$, such that they have the same number of triangles. Therefore, graph $H$ must be a complete graph. Now, consider the maximal degree of graph $G$. Case 01. If its maximal degree is $2$, the we know that $G$ is a simple chain that has length $n$. (It could be closed, or closed - which is a circuit $C_n$ in this case.) It's easy to investigate the behavior of $C_n$, which is For odd values of $n$, $C_n'$ is isomorphic to $C_n$, and therefore proved the result. For even values of $n$, $C_n'$ is a disconnected graph of 2 circuit $C_{\frac{n}{2}}$. Therefore, $C_n$ and $(C_n')'$ won't be isomorphic. For the other case, where it is not a closed path, number the vertex with $1, 2, 3, \dots, n$. Notice that $G'$ will be 2 disconnected graph: which is a collection of vertex with even numbers and odd numbers. Therefore, $G$ and $(G')'$ can't be isomorphic in this case. Case 02. If the maximal degree is greater than $2$. Let it be vertex $v$. By Lemma 02, then the subgraph containing $v$ must be a complete graph. Hence, every vertex connected to $v$ only connected to the vertex that is connected to $v$, by the maximality of $v$. Therefore, there can't be any vertex $w$, that is not connected to $v$ , connects to any other vertex in this complete graph. Therefore, $w$ is disconnected from this graph. Since we assumed that our original graph is connected, then it must be a complete graph. Notice that $(K_n)' = K_n$ for every $n$, and therefore $G$ is isomorphic to $G'$. Case 03. If its maximal degree is $1$, which means that this vertex is isolated from the others. There's nothing to prove. Remark. In fact, we can characterize all the graph satisfying the condition of the problem: which is just an isolated vertex, a circuit $C_n$ and a complete graph $K_n$.

Call the operation $\textit{changing}$ the graph. Say a graph $G$ satisfies $(G')'$ is isomorphic to $G$. Note that triangles are preserved under changings, so the number of triangles is nondecreasing between changings. Thus, no new triangles can be made through changings. Call vertices that are contained in some triangle $\textit{good}$. The number of good vertices is also nondecreasing between changings. Therefore it must be constant. Consider any maximal clique $C$. If $|C| \geq 3$. Say there's some vertex attached to $C$. Note that after one operation, that vertex will create a triangle. Therefore there can't be a vertex attached to $C$ that's not a part of $C$. Thus for any connected component that contains a triangle, it must simply be a clique. Now say $|C| <3$. Say a vertex in $C$ is connected to at least $3$ vertices. We create a triangle in the next changing, so this can't happen. Thus we must either have a path or a cycle. It's easy to check only odd cycles work. Thus $G$ must be decomposable into odd cycles and cliques that are disjoint. It's easy to verify that $G = G'$.

Notice that connected components are preserved, therefore it suffices to deal with the case that the graph is connected. Now, let the largest clique in $(G')'$ has size $n$. Since $G$ is isomorphic to $(G')'$, there is also a clique with size $n$ in $G$. Now we divide into two cases: CASE I: $n\geq 3$ Let the clique in $G$ be $V_1,V_2,...,V_n$ Suppose there are some other vertices $V$ that is adjacent to $V_1$, then $V$ is adjacent to $V_2,V_3,...,V_n$ in $G'$, moreover $V_1,V_2,...,V_n$ is still a clique in $G'$. Therefore, $V,V_1,...,V_n$ is a clique in $(G')'$, which contradicts the fact that the largest clique in $(G')'$ has size $n$. Therefore, since $G$ is connected, it must be a complete graph, from which the condition is easily satisfied. CASE II: $n=2$ If a vertex in $G$ has degree $m\geq 3$, then its adjacent vertices form a clique in $G'$, hence also form a clique with size $m$ in $(G')'$, contradiction. Therefore, the graph must be a chain or a cycle. From which the problem follows from direct checking.

If $v_1, v_2, \ldots , v_{2n+1}$ form an odd cycle in $G$, then $v_1, v_3, \ldots , v_{2n+1}, v_2, v_4, \ldots , v_{2n}$ form an odd cycle in $G'$. It follows that the number of odd cycles in $G'$ is at least the number of odd cycles in $G$. Since $(G')' = G$, no other odd cycles than the ones arising from odd cycles in $G$ may exist in $G'$. In particular, if $v$ is a vertex with degree $d \ge 3$, then the neighbors $v_1, \ldots , v_d$ of $v$ are connected by edges to each other. Hence the neighbors have degree at least $3$ and have the same property. Thus, they cannot have a neighbor $w \not\in \{v, v_1, \ldots , v_d\}$, as otherwise $v$ and $w$ would not be connected by an edge. Hence each vertex has degree at most two or belongs to a clique. Note that the number of components is non-decreasing under $'$, so to have $G \cong (G')'$, no components may split into several components when performing $G \to G'$. This is seen to imply that $G$ consists of odd cycles and cliques. In this case one clearly has $G \cong G'$.

Really nice! In what follows, we assume that $G$ contains at least $3$ vertices (cases where $|G| < 3$ are easily checkable by hand). We will prove by induction on $|G|$ that $G$ is a disjoint union of cliques and odd cycles, with base cases $|G| < 3$ trivial. Additionally, we discard all $1$-vertex connected components (as these are fixed by the operation). Let $v$ be the vertex with maximal degree in $G$, and let $d = \deg(v)$. We first tackle the case where $d > 2$. Consider the subgraph containing $v$ and its neighbors. In $G'$, each of the neighbors of $v$ will be connected, implying that $G'$ contains a $d$-clique. It follows that $(G')'$ will also contain a $d$-clique (since $d > 2$, the $d$-clique from $G'$ will be preserved by the operation). As $G$ and $(G')'$ are isomorphic, it follows that $G$ contains a $d$-clique $S_d$. In the case that there is no vertex $v \not\in S_d$ which is adjacent to $S_d$, we find that $S_d$ is a connected component of $G$, whence we may delete it and induct down. Otherwise, suppose such a vertex $v$ exists, and let it be adjacent to $u \in S_d$. Then, in $G'$ all vertices of $S_d$ will be connected (for each $a, b \in S_d$ we have a cherry $acb$), while $v$ will be connected to each vertex in $S_d$, with the potential exception of $u$ (for each $b \neq u$, we have the cherry $vbu$). Now, in $(G')'$, the induced subgraph on $S_d \cup v$ is a $(d + 1)$-clique: as with $G'$ the induced subgraph on $S_d$ is a $d$-clique, and for each vertex $b \in S_d$ we have a cherry $vcb$. In particular, by isomorphism, $G$ contains a $(d + 1)$-clique as well. Since the maximal degree of $G$ is $d$, this $(d + 1)$-clique must be in its own connected component, whence we may once delete it and induct down. To finish, we handle the cases where $d = 1, 2$. In the case that $d = 1$, $G$ must be a disjoint union of $K_2$'s, in which case the problem is obvious. Meanwhile, if $d = 2$, we find that $G$ is a union of disjoint cycles and lines. Let $v_1v_2\cdots v_n$ be the minimal connected component of $G$. Suppose this component is a cycle, where $v_i$ is adjacent to $v_{i - 1}$ and $v_{i + 1}$ for each $i$ (indices mod $n$). If $n$ is even, in $G'$ the cycle $v_1\cdots v_n$ splits into disjoint cycles $v_1v_3\cdots v_{2n - 1}$ and $v_2v_4\cdots v_{2n}$; hence, the minimal connected component of $(G')'$ is smaller than the minimal connected component of $G$, contradicting the fact that they are isomorphic. If $n$ is odd, we may delete the component $v_1v_2\cdots v_n$ from the graph and induct down. Finally, we show that $v_1v_2\cdots v_n$ cannot be a line graph. In this case, suppose $v_i$ is adjacent to $v_{i - 1}$ and $v_{i + 1}$ for $2 \leq i \leq n - 1$. In $G'$, the line $v_1v_2\cdots v_n$ splits into two lines $v_1v_3\cdots$ and $v_2v_4\cdots$, implying that the minimal connected component of $(G')'$ has size smaller than the minimal connected component of $G$, contradicting the fact that they are isomorphic. Thus, our induction is complete, so if $G$ and $(G')'$ are isomorphic $G$ is a disjoint union of cliques and odd cycles. Meanwhile, in that case, it is easy to check that $G, G', (G')'$ are all isomorphic to each other, completing the proof. $\Box$

First, note that cliques will always stay the same under the operation $(').$ Define a maximal cycle as a cycle $S \in G,$ such that there doesn't exist a cycle $C \in G$ such that $S \subset C.$ Also, WLOG $G$ is connected (otherwise we can split into its connected components). Note that a clique in $G$ will always be a clique in $G.$ Lemma 1: A maximal cycle cannot be connected by an edge to a vertex (or multiple vertices) Proof. For a cycle to be connected to the rest of the graph under $('),$ all of its vertices must be connected to some vertices outside the cycle. There are two possibilities:

All the vertices of a maximal cycle are connected to one vertex outside the cycle If the maximal cycle is $v_1 \sim v_2 \sim \cdots, \sim v_5,$ and the vertex outside the cycle is $v_6,$ we get a larger cycle. Specifically, $v_6 \sim v_5 \sim v_1 \sim \dots \sim v_4 \sim v_6$ which is a contradiction.

Let the maximal cycle be $v_1 \sim v_2 \sim \cdots \sim v_5,$ as in the previous case, and the outside vertices be $v_6$ and $v_7.$ But since $G$ is connected, $v_2v_5$ must be an edge and so must $v_7v_5$ for $G'$ to still be connected. But this is a contradiction, since $v_5 \sim v_7 \sim v_1 \cdots v_4 \sim v_5 \sim v_7$ becomes is now a longer cycle than $v_1 \sim v_2 \sim \cdots \sim v_5,$ Lemma 1 implies that G is just a set of disjoint cycles (with possibly edges connecting two vertices in the cycle), cliques and/or paths. Paths are obviously not possible, because that would disconnect the graph. So G is a set of disjoint cliques and/or cycles. Note that there cannot be an edge connecting two vertices in a cycle, because under the operation, it does not map onto itself, and so does no other types of cycles with edges, contradicting the bijection between $G$ and $G'.$ Its easy to see G cannot have an even cycle, because that would disconnect the graph. Finally, its easy to check that G being a set of disjoint cliques and odd cycles works. We are done because all cases have been covered.

Hard for a #4, but really nice! Replace $\bullet '$ with $f(\bullet)$. We start off with some easy observations. If $G=H_1\sqcup H_2\sqcup \dots H_k$, then, $f(G)= f(H_1)\sqcup f(H_2)\sqcup \dots f(H_k)$. In other words, the connected components of $G$ dont talk to each other, so we can WLOG assume $G$ to be connected. $f(K_n)\cong K_n$ and $f(C_{2n+1})\cong C_{2n+1}$. The above observations tells us that the number of triangles is non-decreasing after every application of $f$. Since the number of triangles in $f(f(G))$ is the same as that of $G$, hence applying $f$ on $G$ must never create a new triangle. Pick the maximal clique of size $n$ of G. Now we divide into cases based on size of $n$. Case 1 : $n\ge 3$. We claim that $G$ is a clique. Consider the maximal clique $v_1,v_2,\dots v_n$of $G$ and assume that there is some vertex $v\neq v_i$ such that $vv_1$ is a edge. Then in $f(G)$, all of $vv_i$ for $2\le i\le n$ must be a edge. Hence in $f(f(G))$, we must have that $vv_1$ and $vv_i$ for all $3\le i\le n$ is a edge. However since $v_2$ was a common neighbor of $v$ and $v_3$ in $f(G)$, hence $f(f(G))$ must have $vv_2$ as a edge as well. Hence this gives that the size of maximal clique in $f(f(G))$ is $\ge n+1$, which is a contradiction. Case 2 : $n<3$. We claim that $G$ must be an odd cycle. Note that if any vertex $v$ in $G$ has $\ge 3$ neighbours, then those neighbors form a triangle in $f(G)$, which is a contradiction. Hence $G$ is a connected degree with every vertex having degree $\leq 2$. We have only three following cases : If $G$ is a even cycle. Its obvious to see that it cant hold. If $G$ is a tree. Note that since $\deg v \leq 2$, $G$ is actually just a simple path. Hence, $f(G)$ is disconnected, which is a contradiction. Hence $G$ must be a odd cycle, as desired. Having exhausted all cases, we are done. $\square$

v_Enhance wrote: For a finite simple graph $G$, we define $G'$ to be the graph on the same vertex set as $G$, where for any two vertices $u \neq v$, the pair $\{u,v\}$ is an edge of $G'$ if and only if $u$ and $v$ have a common neighbor in $G$. Prove that if $G$ is a finite simple graph which is isomorphic to $(G')'$, then $G$ is also isomorphic to $G'$. Mehtaab Sawhney and Zack Chroman Time to post my solution. Replace $G'$ by $P(G)$. It suffices to prove the claim for all connected graphs $G$, as any graph $G_1$ is a union of mutually disjoint connected graphs. Let us say that $G$ is not a clique, otherwise the result trivially holds true. It can be seen that $\omega(P(P(G))) \geq \omega (P(G)) \geq \omega(G)$. Therefore if $P(P(G)) \sim G$, then $\omega(P(P(G))) = \omega (P(G)) = \omega(G)$. If there exists a clique $H$ of size at least $3$ which is a subgraph to $G$, choose $H$ to be a maximal clique, then consider a vertex $v \in G$ such that $v \not\in H$ and $v$ is connected to a vertex $u \in H$, then all vertices $u_1 \in H$ except $u$ will be adjacent to $v$ in $P(G)$ and therefore the vertex $v$ and all the vertices in $H$ form a clique of size $\omega(G) + 1$ in $P(P(G))$, which contradicts the fact that $\omega(G) = \omega(P(P(G))$. Therefore, it follows that $G$ has no clique of size at least $3$. Therefore, if there exists a vertex $v \in G$ satisfying $\text{deg}_G(v) \geq 3$, then the vertices belonging to the open neighbourhood of $G$ form a clique of size at least $\text{deg}_v(G) \geq 3$, this means that $\omega(G) = \omega(P(G)) \geq \text{deg}_G(v) \geq 3$, a contradiction. Therefore each vertex $v \in G$ has degree at most $2$, forcing $G$ to be a tree or a cycle. We see that if $G$ is an cycle of even size, then $P(G)$ is composed of two mutually disjoint cycles which means $G \not\sim P(P(G))$. If $G$ is a cycle of odd size, it can be easily seen that in case of odd cycles $G$, $G \sim P(G) \sim P(P(G))$ as desired. If $G$ is a tree, we see that the graph must be a line graph, but line graph will get disconnected after application of $P$. Therefore $G$ is either a clique or an odd cycle if $G \sim P(P(G))$ and in both the cases, our assertion $G \sim P(G)$ holds true as desired.

The key idea is to look at triangles in the graph. Note that the operation preserves triangles and since we have $G$ is isomorphic to $(G')'$, the number of triangles in both must be same, so no new triangle can have been formed. I claim that the only possible such graphs are ones which have cliques and odd cycles as their connected components. Call a vertex big if it has degree at least $3$. Let $v$ be a big vertex, pick three neighbours of it, say $a,b,c$. If $abc$ is not a triangle, then the triangle $abc$ is created next, which should not happen. So we have that any big vertex is part of a clique. Note that any other vertex connected to the clique also must be part of it. Since the operation preserves cliques too, we can delete it and induct. So now suppose every vertex has degree at most $2$, this means that every connected component is either a chain or a cycle. If there is an even cycle or a chain, then observe that the operation splits it into two connected components. Since $(G')'$ has only as many connected components as $G$, this can't happen since the operation does not merge connected components. Therefore $G$ is indeed just a combination of cliques and odd cycles, as claimed. It's easy to see that in such cases, the operation leaves the graph isomorphic to what it was originally, so we are done. $\blacksquare$

v_Enhance wrote: For a finite simple graph $G$, we define $G'$ to be the graph on the same vertex set as $G$, where for any two vertices $u \neq v$, the pair $\{u,v\}$ is an edge of $G'$ if and only if $u$ and $v$ have a common neighbor in $G$. Prove that if $G$ is a finite simple graph which is isomorphic to $(G')'$, then $G$ is also isomorphic to $G'$. Mehtaab Sawhney and Zack Chroman

Cool Replace $'$ with $f$. I claim that any $G$ which satisfies $f(f(G))=G$ must be comprised of the union of odd cycles or complete graphs with at least three vertices. We can then easily check that for all such graphs, we also have $f(G)=G$, since odd cycles get mapped to isomorphic odd cycles and complete graphs (with at least three vertices) get mapped to themselves. Note that $f$ only ever decreases the number of connected components, so for the condition to hold $f$ can never disconnect any connected component of $G$. Thus no connected component of $G$ or $f(G)$ may be bipartite. We are ready to solve the problem by downwards induction on the number of connected components, with the base case of $0$ components being obvious. To do this, consider the highest degree vertex of $f(G)$, and call that degree $m$. We have the two following cases: Case 1: $m<3$. Then every connected component of $f(G)$ is clearly either a line or a cycle. But since no connected component may be bipartite, we can eliminate every possibility except for odd cycles. But if $f(G)$ is all odd cycles, then by considering each connected component $f(f(G))=G$ is also all odd cycles as desired. Case 2: $m \geq 3$. Then let $w_1,\ldots,w_m$ be the vertices adjacent to the vertex $w$ of maximal degree. Applying $f$ to $f(G)$ then connects any $w_i$ to $w_j$ through $w_i-w-w_j$, so we get a complete graph $K_m$ in $f(f(G))=G$. Now, let $n$ be the largest integer such that $G$ has a $K_n$ subgraph with vertices $v_1,\ldots,v_n$, so $n \geq 3$. I will prove that nothing is connected to this $K_n$. Suppose that we did have some $v$ connected WLOG to $v_1$. Then in $f(G)$, all edges $\overline{v_iv_j}$ exist by taking $v_i-v_k-v_j$ for some $k \neq i,j$ (the existence of such $k$ is why we need $n \geq 3$), and all edges $\overline{vv_i}$ exist for $i \neq 1$ by taking $v-v_1-v_i$. Then, in $f(f(G))$, all edges $\overline{v_iv_j}$ still exist, all edges $\overline{vv_i}$ exist by taking $v-v_j-v_i$ for $j \neq i$. But then $v,v_1,\ldots,v_n$ are all connected to each other, forming a $K_{n+1}$ in $f(f(G))=G$. This contradicts the maximality of $n$, so no vertices can be connected to the $K_n$. Then $f$ doesn't change that $K_n$ at all, so we can remove it and induct down on the number of connected components. $\blacksquare$

First, notice $K_3$ subgraphs are conserved under $G$. Hence no new triangles can be created, so for any vertex of degree $3$, its neighbors form a clique, and all of their degrees are at least $3$, so its connected component must be a clique. If a connected component has all vertices of degree at most $2$, then it is either a path or a cycle, and casework demonstrates easily that only odd cycles survive. Hence $G$ is a disjoint union of odd cycles and cliques, so we are trivially done.

Note that each triangle in $G$ stays as a triangle in $G'$. Thus, if $(G')'$ is isomorphic to $G$, then they have the same number of triangles, which means that no additional triangles can be created when going from $G$ to $G'$ or going from $G'$ to $(G')'$. Claim: For all $n\geq3$, if a vertex has degree $n$, it must be part of a $K_{n+1}$. Consider a vertex $A$ in graph $G$ with degree $n$ that is connected to $B_1,B_2\cdots B_n$. In $G'$, the vertices $B_1,B_2\cdots B_n$ form a $K_n$ since any pair has a common neighbor $A$. Thus, since we know that no new triangles are created, $B_1,B_2\cdots B_n$ must be a $K_n$ in the original graph $G$ as well. Hence, $A$ is part of a $K_{n+1}$. Clearly, any $K_n$ stays invariant under $G\rightarrow G'.$ It remains to consider the vertices with degree 2 or lower. Any connected component where the degree of each vertex is at most 2 is either a cycle or a path. A path simply disappears upon applying $G\rightarrow G',$ so there are no paths in $G$. Furthermore, odd cycles stay the same under $G\rightarrow G''$ (in fact they stay the same under $G\rightarrow G'$), while even cycles do not. Hence, $G$ consists of only cliques and odd cycles, so we are done.

Any triangle in $G$ remains in $G'$, so the number of triangles is non-decreasing so no triangles can be made. Thus, if vertex $A$ is connected to vertices $P_1, P_2,\ldots, P_k$ then $P_iP_jP_l$ is a triangle for distinct $1\leq i,j,l\leq k$. But this means each of these were a triangle to begin with, so $A, P_1, P_2,\ldots, P_k$ form a clique in $G$. Any connected component containing such a clique of size at least $3$ must not include any other vertices - if vertex $B$ is connected to clique vertex $P_t$ in $P_1\ldots P_k$ but $BP_1\ldots P_k$ is not a clique, then in $G'$, the number of triangles increase as $BP_iP_j$ that wasn't a triangle before becomes a triangle for some distinct $i,j\neq t$. Therefore, any connected component containing a clique ONLY contains that clique. Now, since connected components do not interact with each other, consider the connected components $C_1, C_2,\ldots, C_k$ of vertices with degree at most $2$ (degree at least $3$ implies clique as proven before). Thus, the $C_i$ are trees or cycles. If the list $C_1,\ldots, C_k$ is the same as the list $(C_1')', \ldots, (C_k')'$ in some order, then there exists some finite $n$ (in fact, $n\leq k!$) such that $n$ applications of $'$ to each $C_i$ is isomorphic to $C_i$ for all $1\leq i\leq k$. It now suffices to show that $G'$ is isomorphic to $G$ if after $n\geq 1$ applications of $'$ it returns to $G$. Case 1: $C_i$ is a tree. Then since each vertex has degree at most $2$, then it has vertices $P_1, \ldots, P_m$ such that $P_iP_{i+1}$ is an edge for $1\leq i\leq m-1$. But then $G'$ splits into two connected components, a contradiction, since the original graph will now have at least $k+1$ non-clique connected components no matter how many applications of $'$. Otherwise, $G$ has one vertex, meaning $G'$ is isomorphic to $G$. Case 2: $G$ is a cycle. If $G$ is an even cycle $P_1P_2,\ldots P_{2x}$ then $G'$ will split off into two connected components $P_1P_3\ldots P_{2x-1}$ and $P_2P_4\ldots P_{2x}$, a similar contradiction. Thus, $G$ is an odd cycle, so $G'$ is isomorphic to $G$ (same odd cycle) as needed.

In linear algebra terms we need to prove the following. Quote: Let $A$ be an $n \times n$ matrix, and suppose that $A$ is symmetric with a zero diagonal and has all entries $0$ or $1$. Let $F(M)$ be $M$ where the 0 entries become $0$ and all other entries become $1$. Show that $A \sim F(F(A^2)^2)$ implies $A \sim F(A^2)$. Can I get a hint for proving this? If this seems unreasonable, feel free to let me know. I know that if I prove that $M \sim F(M)$ for all square matrices and that $M$ and $M \sim M^2 \sim M^4$ for all matrices $M$ that are symmetric and have a $0$ diagonal, then I am done.

I didn't find this particularly hard for TST1, maybe as it's decisively rigid, but this problem is really fun to think about. The key claim is the following: Claim. If $\deg v = n \geq 3$ for some $v \in G$, then $v$ is part of a $K_{n+1}$. Proof. Notice that if a triangle $T \in G$, then $T \in G'$. Furthermore, the number of triangles cannot strictly increase. Now assume the contrary. Then, there exist three neighbors $v_1, v_2, v_3$ of $v$ such that they do not form a triangle. On the other hand, $v_1, v_2, v_3$ form a triangle in $G'$, hence contradiction. $\blacksquare$ Claim. $G$ is isomorphic to $G''$ if and only if it is a union of vertex-disjoint cliques and odd cycles. Proof. We already proved that if $\deg v \geq 3$, then $v$ is part of a disjoint clique. Now, observe that if $u$ and $v$ are disconnected in $G$, they cannot be connected in $G'$. Thus it suffices to look at connected components for vertices $\deg v \leq 2$. For any even cycle, the cycle becomes two disjoint cycles under the operation, which is a clear contradiction; similarly, any path becomes two disjoint paths. The only components of $G$ that are preserved are odd cycles. $\blacksquare$ On the other hand, any $G$ which satisfies the above conditions also has $G = G'$, hence done.

Begin with the following key results: Any clique $K_n$ can only remain the same or increase in size after an operation (Every vertex has a path of length 2 from any other vertex) If vertex $v$ satisfies $\deg v \geq 3$, its neighbors form a clique $K_{\deg v}$ (Again, every pair of neighbors has $v$ as a shared neighbor) Consider any clique $K \in G$. If $K$ is connected with graph $G-K$ then the size of $K$ will increase. This makes it impossible for $G \equiv (G')'$ by comparing the set of cliques. Thus, all cliques must be their own connected components. The remaining connected components must have no cliques. Then after one operation, any vertex $v$ with $\deg v\geq 3$ will turn into a clique and this clique will grow or remain, meaning $G$ must have less cliques than $(G')'$, a contradiction. This implies all connected components which are not cliques have all vertices degree $1$ or $2$ implying either linked-lists or cycles. Note that the operation doesn't alter odd cycles whereas it splits even cycles into two cycles. It also splits linked-lists into multiple linked lists. Thus if we have any even cycle or linked-list the quantity will strictly increase over two operations, and thus $G \neq (G')'$. This means $G$ can only consist of disjoint cliques or odd-cycles, both of which remain the same after an operation. Thus we must have $G$ is isomorphic to $G'$.

Note that the number of triangles in $(G')'$ is the same as $G$. Claim: If $G$ has a vertex of degree at least $3$ then $G$ is a complete graph. Proof. Let vertex $v$ have degree at least $3$, with neighbors $N$. Then by the triangle monovariant it follows that $\{v\} \cup N$ must be a complete graph. Likewise, if $N$ has any neighbor $w \ne v, w \not\in N$, then it follows that $v$ and $w$ are neighbors in $G'$, contradicting the triangle monovariant in $G''$. $\blacksquare$ Now, if $G$ only has vertices of degree $2$ or less, we can decompose $G$ into a series of paths and cycles. It remains to show the result for each path and cycle. Claim: $G \ne (G')'$ for paths. Proof. Enumerate the path $a_1, \dots, a_n$. Then $a_k, a_{k+4}$ are neighbors in $(G')'$, which splits the path into multiple. $\blacksquare$ Claim: If $G$ is a cycle, $G = (G')'$ if and only if it has length $n$ not divisible by $2$. Proof. If the length is divisible by $2$, $(G')'$ once again splits into multiple disjoint cycles. Else, since $\gcd(4, n) = 1$, $G'$ is a cycle and thus $(G')'$ is a cycle. $\blacksquare$ This finishes.

Note that the number of triangles in $G''$ is the same as the number of triangles in $G.$ As all triangles are preserved, $G'$ has the same number of triangles too. Consider a vertice in $G$ with degree $n \geq 3.$ In order to not make any new triangles, everything adjacent to this vertice also needs to be adjacent to one another. Thus, if and only if a vertice has degree $n \geq 3,$ it is a part of a $K_{n+1}$ connected component. Now, for $n \leq 2.$ By the above , we know that vertices of $n=1$ and $2$ can only be adjacent to vertices of $n=1$ and $2.$ Thus, these vertices form either paths or cycles. Paths get split up into two disjoint paths, so they don't work. Even cycles also get split up into two disjoint cycles. However the one thing that does work is odd cycles, which turn into a permutation of themselves. Thus, we can only have connected components that are either odd cycles or cliques. As both of these turn into a permutation of themselves or stay the same, respectively, $G'$ is isomorphic to $G,$ so we're done.

Call a triple of vertices $(a,b,c)$ a "triangle" if there is an edge between each pair of vertices. Note that the number of triangles in $G'$ is at least as many as in $G$, since existing triangles are preserved by the operation. So, if $(G')'$ is isomorphic to $G$, there must be no new triangles created in $G'$ or $(G')'$. Consider any vertex $v$ with degree $3$ or greater in $G$ – in $G'$, the neighbors of $v$ will form a clique. Since we can't create any new triangles, this clique must have already existed beforehand – every vertex in $G$ must form a clique with all of its neighbors. Claim: If every vertex of a component forms a clique with its neighbors, the component itself is a clique. Proof: Consider a clique and a vertex $v$ attached to the clique. But then if $v$ is attached to the clique at a vertex $u$, by applying the assumption on $u$, every vertex in the clique has an edge to $v$, so our clique just got bigger. We can repeat this until the whole component is a clique. Therefore, every component in $G$ must either be a clique or have every vertex have degree $1$ or $2$. In the latter case, note that the only such graph we may have is a cycle of odd length, since paths and cycles of even length break up into more components (obviously, two components cannot merge together). From this, it follows that not only is $G$ isomorphic to $G'$, but each component is isomorphic to itself.

If all vertices of $G$ have degree at most $2$, then it is the union of paths and cycles, which can be easily verified to work if and only if $G$ is the union of odd cycles and single vertices. Otherwise, if a vertex of $G$ has degree at least three, then $G'$ has a $K_3$, so $(G')'$ also has a $K_3$. Consider the largest clique $K_n$ in $G$ where $n\geq3$. This clique remains in $G'$ and $(G')'$. If any other vertex $u$ is connected to the clique in $G$, then in $G'$, $u$ is connected to every vertex in the clique other than the original vertex it was connected to, so $u$ is connected to every vertex in the clique in $(G')'$, contradicting the maximality of $n$. Therefore, $K_n$ must be a single connected component, which means that $G$ is the union of cliques, odd cycles, and single vertices, so $G$ is isomorphic to $G'$.

Let $f$ be a function mapping graphs $G$ to their graph $G'$ defined by the operation, and let $g$ of a graph be the number of triangles, clearly we have that $g(f^k(G))\geq g(f^m(G))$ if $k\geq m$, now suppose there exists a vertice $v$ such that the degree of $v$ is $\geq 3$ and such that all the vertices that are connected to $v$ do not form a clique with each other, this implies that a new triangle will be added and $g$ will increase which implies the degree of all vertices is $\leq 2$ or $G$ is made up of individual cliques, and clearly if $G$ is an even cycle the $f(f(G))=G$ doesn't hold and if its a path also doesnt hold and if its odd cycle it holds so if $f(f(G))=G$ $f(G)=G$.