Maximum number of edges in a graph where length of every cycle is a multiple of 3

Question

I am doing a problem which asks to find the maximum number of edges in a graph on $n$ vertices which has the property that every cycle's length is a multiple of 3.

I was able to show that if $G$ contains a cycle $C$ then that cycle $C$ can not contain a chord. The answer is $n-1$ +$\left\lfloor{\frac{(n-1)}{2}}\right\rfloor$ edges.

I proceed by induction and assumed the result is true for graph on n vertices. Then if G has $n+1$ vertices then I reduced the problem into three cases:

1. There exists a vertex in G of degree 1 ( then induction takes us home)
2. $\delta(G)$ $\geq$$3$ where $\delta(G)$ is the minimum degree of $G$ (by observing that in this case $G$ must contain a cycle with a chord)
3. When neither of the first two cases hold. I am stuck with this case. Help?

Answer 1

Here's a lemma without proof: Let $G$ be simple with no degree-$2$ vertices and no cut vertices. Then either $G$ is a cycle graph or $G$ has an edge $(v_1, v_2)$ such that its deletion still leaves a graph with no cut vertices. Note that this edge is the chord of a cycle in $G$.

We are done if $G$ is just a cycle, so suppose it is not. Our goal is to find two adjacent vertices that both have degree $2$. By deleting them, you reduce the number of vertices by $2$ and the number of edges by $3$, so you win by induction. Suppose by way of contradiction that there is no such pair of vertices.

First suppose that $G$ has no cut vertex. Let $G'$ be the cosimplification of $G$, that is, the graph obtained by identifying every pair of edges joined by a degree-$2$ vertex. There is an edge $(v_1, v_2)$ that forms a chord of a cycle on $G'$. In $G$, this edge must be subdivided to make a path $P$, and it must be subdivided only once or else we have adjacent degree-$2$ vertices, so $|P| = 2$. Let $C'_1$ and $C'_2$ be cycles of $G'$ that only intersect at $(v_1, v_2)$ (their existence is implied by the lemma), and let $C_1$ and $C_2$ be their corresponding cycles in $G$. Then the disjoint union of $C_1$ and $C_2$ is a cycle in $G$, but it has length

$$0 - 2|P| \equiv 2 \pmod 3$$

which contradicts every cycle having $0 \pmod 3$ edges.

If $G$ has a cut vertex, then choose one such that the deletion separates the graph into parts $K$ and $J$ such that there are no edges between $K$ and $J$, and the order of $K$ is minimal. (In particular, there are no cut vertices within $K$). Then the same argument by contradiction above shows that there must be two degree-$2$ vertices adjacent to each other within $K$.

Answer 2

First a variant of your no-chord lemma. Consider an arbitrary graph where every cycle has length a multiple of $3$, and suppose $$ a_1 - a_2 - a_3 - \cdots - a_{3k} - a_1 $$ is such a cycle. Assume there exists a path $$ a_i - b_1 - b_2 - \cdots - b_m - a_j $$ that contains no edge or intermediate vertex from the cycle. Then prove that $i\equiv j\pmod 3$.

---

Now suppose $G$ is a multiple-of-3-cycle graph with $n$ nodes and a maximal amount of edges. Then I will argue that $G$ cannot have a simple cycle $$ a_1 - a_2 - a_3 - \cdots - a_{3k} - a_1 $$ where $k>1$. Namely, if it does. then we can collapse it to a triangle by identifying nodes whose indices are congruent modulo $3$. After this collapse, the graph still satisfies the multiple-of-3 condition: If it has a new cycle (other than the collapsed triangle) that wasn't present before, then that cycle must involve one of the collapsed nodes, but then the above lemma says it cannot involve more than one of the nodes and it corresponds to a cycle in the original graph that includes a multiple of $3$ edges in the collapsed cycle -- so there's a multiple of $3$ edges left in the collapsed graph too.

The collapse reduced both the number of nodes and the number of edges by $3(k-1)$, but we can arrange those in $k-1$ new fragments of the shape

      O
     / \
<---O---O

and attach each of those somewhere. Each fragment contributes four new edges, so we end up with more edges than we had but the same number of nodes -- contradicting the assumption that $G$ had a maximal number of edges.

So now we know that $G$ must be a tree made of triangles and single edges. And it is easily shown by induction that a graph of that shape has at most $n-1+\lfloor\frac{n-1}2\rfloor$ edges.

---

On the other hand, it is easy to see that $n-1+\lfloor\frac{n-1}2\rfloor$ edges can be achieved, by having one vertex have degree $n-1$ and connecting its neighbors two by two into $\lfloor\frac{n-1}2\rfloor$ triangles that share a corner (with a leaf vertex left over if $n$ is even).