4
$\begingroup$

Does every graph $G$ contain a triangle-free subgraph $H$ such that $H \cup e$ contains exactly one triangle for every $e \in E(G) \setminus E(H)$? Consider the following examples: enter image description here

Note that if $G$ is triangle-free, we may take $H=G$. Also, if $G$ contains a spanning tree $T$ which is a star, we may take $H=T$.

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ Are you defining maximal triangle-free to mean that adding any edge creates exactly one triangle? If so, a 4-cycle does not have one. Adding any edge creates 2 triangles; but in any proper subgraph there exist edges to add that create no triangles. $\endgroup$
    – benblumsmith
    Commented Nov 18, 2016 at 20:04
  • $\begingroup$ Of course, "maximal triangle-free subgraph" to me ought to mean a subgraph $H$ that is maximal among all triangle-free sungraphs. And if that's all that's meant, there's not much to prove here. $\endgroup$
    – Pat Devlin
    Commented Nov 19, 2016 at 1:45
  • 1
    $\begingroup$ @WłodzimierzHolsztyński To clarify the problem: 1- When I say $H$ is a subset of $G$ and we add a missing edge to $H$, I mean we add an edge from $G$ which is missing in $H$. 2- For the case when $G$ has no triangle, $H$=$G$. 3- If $G$ has only 1 triangle, we can remove arbitrarily one edge of the triangle and call it $H$. Because by adding back that edge to $H$ we can reconstruct only 1 triangle. $\endgroup$
    – Nikan
    Commented Nov 21, 2016 at 22:48
  • 1
    $\begingroup$ 4- For the cases with 2 triangles in $G$, There are 2 possibilities: a) The 2 Triangles doesn't share any edge, so we can remove arbitrarily 1 edge from each triangle and call it $H$. b) The 2 Triangles share an edge, we remove an edge from the other (not shared) edges of the triangles and call it $H$ 5- For the cases with more than 2 triangles, I have no idea if $H$ exists!! $\endgroup$
    – Nikan
    Commented Nov 21, 2016 at 22:48
  • 1
    $\begingroup$ I clarified the question and took the liberty of un-naming the concept since the old name of 'maximal triangle-free subgraph' elicited confusion. Feel free to rename the concept if you like. $\endgroup$
    – Tony Huynh
    Commented Oct 18, 2020 at 7:37

1 Answer 1

Reset to default
3
$\begingroup$

This is false. Here is how to construct a counterexample.
Suppose $abc$ is a triangle in $G$.
Also suppose that there are many (at least two) vertices in $G$ whose only neighbors are $a,b,c$.
A simple case analysis shows that $H$ must contain exactly two edges of $abc$.
If we start with a $K_5$ or larger clique, then add many vertices to each of their triangles in the above described way, we get a contradiction.
In fact, we can even start with a $K_4$, as its only subgraph satisfying exactly two edges from each triangle is a $C_4$, but that does not lead to a solution.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Nice! However, $K_4$ and the diamond both have a subgraph which contains exactly two edges from each triangle. Shouldn't you use $K_5$ for the construction (which does not have this property)? $\endgroup$
    – Tony Huynh
    Commented Oct 18, 2020 at 12:47
  • $\begingroup$ @TonyHuynh : I didn't really understand the answer above. I'm sure it's correct. But for $K_5$ a clear subgraph with the required property would be any one of the 24 $5$-cycles (pentagonal paths). $\endgroup$
    – Yaakov Baruch
    Commented Oct 18, 2020 at 13:22
  • 2
    $\begingroup$ @YaakovBaruch I meant that $K_5$ does not have a subgraph such that every triangle of $K_5$ contains exactly two edges of the subgraph. This is what is used in the final part of the above argument. So the final counterexample is obtained by doing the construction on each triangle of $K_5$. $\endgroup$
    – Tony Huynh
    Commented Oct 18, 2020 at 13:29
  • $\begingroup$ @Tony Indeed, you're half-right! The diamond doesn't work, but $K_4$ does, because its only subgraph with two edges from each triangle is the $C_4$, which is ultimately bad. $\endgroup$
    – domotorp
    Commented Oct 18, 2020 at 15:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .