Introduction to Graph Theory · Problem 2.7

Simple graphs — Darij Grinberg

Mathematics — Graph Theory · common-neighbors-parity

Problem

Let nn be a positive integer. Let SS be a simple graph with 2n2n vertices. Prove that SS has two distinct vertices that have an even number of common neighbors.

Browse the problem library