Making 7 vertices triangle free graph bipartite by deleting an edge

Question

Can anyone assert or refute the following claim?

Claim:

In every triangle free undirected graph $G=(V,E)$, $|V|=7$, there exist an edge $e\in E$ such that $G'=(V,E\setminus\{e\})$ is bipartite.

Answer 1

Let $G$ be a triangle-free graph with $|V(G)|=7$ and $|E(G)|>0$. If $G$ is bipartite, then $G \backslash e$ is bipartite for any $e \in E(G)$. So assume $G$ is not bipartite, and thus $G$ has an odd cycle as a subgraph, which must be $C_5$ or $C_7$, since $G$ is triangle-free. If $G$ has no $C_5$ subgraph, then $G$ has $C_7$ as a subgraph, but any chord of $C_7$ would create a triangle or $C_5$, so $G \cong C_7$, and $G \backslash e$ is bipartite for any $e \in E(G)$.

Now we may assume $G$ has $C_5$ as a subgraph. Let $V(G) = \{v_1,v_2,v_3,v_4,v_5,v_6,v_7\}$, and assume $C = v_1 v_2 v_3 v_4 v_5 v_1$ is a 5-cycle in $G$. Any chord of $C$ would create a triangle, so all edges of $G$ not in $C$ are between $v_6$ and $v_7$, or between one of $v_6$ or $v_7$ and $C$. Note that neither $v_6$ nor $v_7$ can be adjacent to two adjacent vertices in $C$, since this would form a triangle, so each is adjacent to at most 2 vertices of $C$. Also, if $v_6 v_7 \in E(G)$, then $v_6$ and $v_7$ cannot have a common neighbor since this would create a triangle. These two observations imply that $G$ is a subgraph of one of the following:

Note that in each case, deleting the red edge creates a bipartite graph.

Answer 2

I don't see how that can be true. Suppose $G = K_7$, the complete graph on $7$ vertices. Deleting any edge results in a graph for which there remains at least one triangle; hence it cannot be bipartite.

Answer 3

I assume that this is true and try to prove it.

I would start from the fact that

A graph is bipartite if and only if it does not contain an odd cycle.

Since $G$ does not contain $C_3$, it may contain only $C_5$ and/or $C_7$. So my guess is that the edge $e$ must break all of these cycles by erasing it from the graph.

It also may be useful that

Any triangle free undirected graph with 7 vertices has at most 12 edges - the maximum is attained only on the complete bipartite graph $K_{3,4}$

(I can elaborate if this idea is useful), which may be used to see how many odd cycles the graph can have.

So assuming next that $G$ contains an odd cycle (otherwise we can choose $e$ to be any edge), then $G$ is not bipartite, hence it has at most 11 edges. Next, if $G$ contains $C_7$ but not $C_5$, we can choose $e$ to be any edge in $C_7$, so we can assume next that $G$ contains $C_7$ and $C_5$ which must have at least one common edge (otherwise we get 12 edges in $G$). If there is no more $C_5$ in $G$, we choose $e$ to be a common edge. If there is another $C_5$ in $G$, then ... well, there are some cases to be analyzed ... Can you pick it from here?