Competition problem — Combinatorics

Library / /31 of 397

Combinatorics Difficulty 4.8 AIME Prove it Taiwan

For a graph $G$ and any vertex $x$ in it, use the notation $G - \{x\}$ to denote the new graph obtained by removing the vertex $x$ together with the edges incident to it. Given two graphs $G$ and $H$ , whose vertices are both numbered $1, 2, \dots, n$ with $n \ge 4$ . If for any $1 \le i < j \le n$ , the graph $G - \{i\} - \{j\}$ is isomorphic to the graph $H - \{i\} - \{j\}$ , prove that: the graph $G$ and the graph $H$ are isomorphic.

Solution

Three steps:
$(1)\ |E(G)| = |E(H)|: \text{ by considering } \sum_{i \neq j} |E(G - \{i\} - \{j\})| = C_2^{n-2} |E(G)|.$

$(2)\ \deg_G(i) = \deg_H(i) \text{ for all } i: \text{ fix some } i_0, \text{ consider } \sum_{j \neq i_0} |E(G - \{j\} - \{i_0\})| = (n-3)(|E(G)| - \deg_G(x_0)).$

$(3)\ \text{Define the function } \operatorname{adj}_G(i,j) = 1 \text{ if } i \text{ and } j \text{ are connected by an edge, } \operatorname{adj}_G(i,j) = 0 \text{ if } i \text{ and } j \text{ are not connected by an edge. It is clear that, } |E(G)| - |E(G - \{i\} - \{j\})| = \operatorname{deg}_G(i) + \operatorname{deg}_G(j) - \operatorname{adj}_G(i,j), \\ \text{which leads to } \operatorname{adj}_G(i,j) = \operatorname{adj}_H(i,j) \text{ for all } i,j.$

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.