MathDB

Here

G_{n}

denotes a simple undirected graph with

n

vertices,

K_{n}

denotes the complete graph with

n

vertices,

K_{n,m}

the complete bipartite graph whose components have

m

and

n

vertices, and

C_{n}

a circuit with

n

vertices. The number of edges in the graph

G_{n}

is denoted

e(G_{n})

. (a) Let

p

be a prime. Consider the graph whose vertices are the ordered pairs

(x, y)

with

x, y \in\{0, 1, . . . , p-1\}

and whose edges join vertices

(x, y)

and

(x' , y')

if and only if

xx'+yy'\equiv 1 \pmod{p}

. Prove that this graph does not contain

C_{4}

. (b) Prove that for inﬁnitely many values

n

there is a graph

G_{n}

with

e(G_{n}) \geq \frac{n\sqrt{n}}{2}-n

that does not contain

C_{4}

5