Signed complete graph with all cycles of length $k$ positive

197 Views Asked by At

A $\textit{signed graph}$ is a graph $G$ whose edges are signed either $+$ or $-$. A cycle is $\textit{positive}$ if the product of its edge signs is positive, i.e., it has an even number of negatively signed edges. Otherwise, the cycle is $\textit{negative}$.

So here's an interesting problem I came up with: Consider a signed complete graph $K_n$, where $n\geq 3$. If all cycles of length $k$ are positive, then every cycle in $K_n$ is positive.

I think it's true when at least one edge of $K_n$ is positive ($K_n$ could have all negative edges and $k$ could be even) because I can't find a counterexample! I've been trying to prove it by the contrapositive: If there exists a negative cycle in $K_n$ then there exists a cycle of length $k$ that is negative in $K_n$. I was trying induction on the contrapositive and was able to knock out several cases with the inductive hypothesis. I am trying to solve the case where the negative cycle is of length $n+1$ and I can't find a way to guarantee that you can find a cycle of length $k$. Any ideas??

1

There are 1 best solutions below

2
On

For a $K_n$ graph to only have positive cycles, it must consist either of all positive edges or of two all-positive-edge subgraphs, $K_{m}$ and $K_{n-m}, 0<m<n$, joined exclusively by negative links. (Note that $K_1$ as one of the subgraphs is an option - of course this has zero edges). Any other arrangement allows a negative 3-cycle.

However your assertion will fail on an all-negative-edge $K_n$ if you choose an even $k$, so you might need to specify that $k$ is odd - then I think you can probably prove it from the above description by first showing that an all-negative graph is not allowed, then assuming a positive link somewhere and building out from there.