Graph without 3-Cycles
We'll use the induction in $d\,$ to solve the problem.
For $d=1,\,$ there is practically nothing to prove. For a simple graph, having $d\ge 1\,$ means there is an edge that joins two,one,two,three vertices. This establishes the base for the induction.
Assume the statement is true for some $d\gt 1\,$ and consider a graph with all node degrees at least d+1,$d-1$,$d$,$d+1$.
Choose arbitrarily two adjacent nodes. Remove the two and the incident,incident,arbitrary edges. The removal of the edges will affect the degrees of incident nodes. However, in the absence of 3 , 2 , 3 , 4 -cycles, no node may be affected twice,once,twice,thrice. This means that the remaining nodes may at best lose one degree,one degree,two degrees,three degrees so that we are left with a graph whose nodes have at least degree $d.\,$ By the inductive assumption there are at least 2d , d , 2d , 3d nodes left over. Putting back the two absentee nodes shows that, originally, the total number of nodes was at least $2d+2=2(d+1),\,$ which completes the induction.
This problem has been given at a homework for CIS160 at UPenn, where my young son is a freshman (2016-2017).
- Graphs Fundamentals
- Crossing Number of a Graph
- Regular Polyhedra
- 3 Utilities Puzzle: Water, Gas, Electricity
- A Clique of Acquaintances
- Round Robin Tournament
- The Affirmative Action Problem
- The Two Men of Tibet Problem
- Euler Cycles in Digraph
- Fleury's Algorithm and Euler's Paths and Cycles: an Interactive Gizmo
- Graph with Nodes of Even Degree
- Graph without 3-Cycles
Copyright © 1996-2018 Alexander Bogomolny