Triangle-free graph: Difference between revisions

Latest revision as of 18:06, 28 May 2012

This article defines a property that can be evaluated to true/false for any undirected graph, and is invariant under graph isomorphism. Note that the term "undirected graph" as used here does not allow for loops or parallel edges, so there can be at most one edge between two distinct vertices, the edge is completely described by the vertices it joins, and there can be no edge from a vertex to itself.
View other such properties

Definition

An undirected graph is termed a triangle-free graph if it satisfies the following equivalent conditions:

Its girth is at last 4 (and possibly infinite).
Its clique number is at most 2.
It has no subgraph that is isomorphic to the triangle graph.
It has no induced subgraph that is isomorphic to the triangle graph.

Relation with other properties

Stronger properties

Property	Meaning	Proof of implication	Proof of strictness (reverse implication failure)	Intermediate notions
bipartite graph
tree
forest

@@ Line 9: / Line 9: @@
 # It has no [[subgraph]] that is [[graph isomorphism|isomorphic]] to the [[triangle graph]].
 # It has no [[induced subgraph]] that is [[graph isomorphism|isomorphic]] to the [[triangle graph]].
+==Relation with other properties==
+===Stronger properties===
+{| class="sortable" border="1"
+! Property !! Meaning !! Proof of implication !! Proof of strictness (reverse implication failure) !! Intermediate notions
+|-
+| [[Weaker than::bipartite graph]] || || || ||
+|-
+| [[Weaker than::tree]] || || || ||
+|-
+| [[Weaker than::forest]] || || || ||
+|}