No, consider the Petersen graph and another with no star in the middle but just a simple pentagon. The former has no 4-cycle, but the latter has one.
2 of 2
Sebastian Goette
- 6.8k
- 2
- 36
- 62
JWL
- 146
- 3