This sounds like an interesting problem, although does seem hard for an exam question.
One idea would be to exploit the fact that you are only interested in relatively short paths, so make sure $G_1$ and $G_2$ differ only on a large scale. For instance consider 6 vertex-disjoint $K_t$'s (where $t$ will be chosen later), each with a distinguished vertex. In $G_1$ connect these vertices with paths of length $\sqrt{n}$ in the form of a hexagon. In $G_2$ do the same, but in the form of two disjoint triangles.
Now the graphs are 'locally' the same- it is easy to show they have the same numbers of short paths. The only problem is that these graphs have too few edges. So on the remaining $2n-6(t+\sqrt{n})$ vertices, add a component with the required number of edges to $G_1$ and $G_2$. You will have to choose $t$ suitably to make this work, but this is not difficult.
For each person $P$, let $\|P\|$ denote the number of gatherings $P$ was part of. For each gathering $g$, let $\|g\|$ denote the number of people who participated in the gathering.
Lemma. If $P$ is not part of $g$, then $\|P\| \ge \|g\|$.
Proof. Let $\|g\|=k$ and let $P_1, \dots, P_k$ be the people who participated in $g$. For each $i$, there has to be another gathering $g_i$ where $P$ and $P_i$ shook hands; the gatherings $g_1, \dots, g_k$ must be distinct, because if $g_i = g_j$ then $P_i$ and $P_j$ shake hands twice (once in $g$ and once in $g_i$). Since $P$ participates in all $k$ gatherings $g_1, \dots, g_k$, we have $\|P\| \ge k = \|g\|$. $\qquad\square$
To make use of this fact, we want to number the people $P_1, \dots, P_n$ and the gatherings $g_1, \dots, g_n$ such that $P_i$ does not participate in $g_i$ for $i=1, \dots, n$. This is a perfect matching between the people and the gatherings, in the "nonparticipation" graph where an edge $(P,g)$ means that $P$ was not part of $g$. We check Hall's condition: for any set of $k$ people, there are at least $k$ gatherings that not all of them were part of.
- If $k=1$, we want to know that there's nobody who was part of every gathering. Well, each person shakes hands a total of $n-1$ times, but they shake hands at least once in every gathering, so they're in at most $n-1$ gatherings (and out of at least one).
- If $2 \le k \le n-1$, then there's at most one gathering containing all $k$ people (because they can't shake hands twice), so at least $n-1$ (and therefore at least $k$) gatherings that don't contain all $k$ of them.
- If $k=n$, then there's $n$ gatherings, and no gathering contains all $n$ people.
So now we have inequalities $\|P_1\| \ge \|g_1\|$ through $\|P_n\| \ge \|g_n\|$. Well, both $\|P_1\| + \dots + \|P_n\|$ and $\|g_1\| + \dots + \|g_n\|$ count the number of pairs $(P,g)$ where person $P$ participated in gathering $g$. So the two sums are equal, and this can only happen if $\|P_i\| = \|g_i\|$ for all $i$.
Let's sort the gatherings such that $\|g_1\| \ge \dots \ge \|g_n\|$. Suppose there is a strict inequality here at some point: $\|g_i\| > \|g_{i+1}\|$. Then $\|P_{i+1}\|, \dots, \|P_n\|$ are all less than $\|g_1\|, \dots, \|g_i\|$ and so by the converse of our lemma, $P_{i+1}, \dots, P_n$ all participate in $g_1, \dots, g_i$. This results in two people participating in two gatherings together unless one of two cases holds:
- $i=1$, so $P_2, \dots, P_n$ all participate in $g_1$ together. But then $g_2$ (and all the ones after) can include at most one of $P_2, \dots, P_n$, so $\|g_2\| \le 2$, which is ruled out by the problem.
- $i=n-1$, so $P_n$ participates in all of $g_1, g_2, \dots, g_{n-1}$. But now $\|P_n\| = n-1$, and by assumption $\|P_{n-1}\| > \|P_n\|$: it must be $n$. But we've already shown that nobody can be part of all $n$ gatherings.
So we can't have $\|g_i\| > \|g_{i+1}\|$ for any $i$, which means $\|g_1\| = \dots = \|g_n\|$, which was what we wanted. (Incidentally, it also means that $\|P_1\| = \dots = \|P_n\|$.)
The proof above is an adaptation of the proof in this 1948 paper by de Bruijn and Erdos. That paper actually analyzes this case as a side note: it shows that without the requirement that there are only $n$ gatherings, there must always be at least $n$.
If all gatherings have size $k$, then we have $\binom n2 = n \binom k2$, which simplifies to $n = k^2-k+1$. There are constructions where this works for many, but not all, $k$. For example:
- When $k=3$, number the people $1, 2, \dots, 7$ and take the gatherings whose participants are the sets $\{1, 2, 3\}$, $\{1,4,5\}$, $\{1,6,7\}$, $\{2,4,6\}$, $\{2,5,7\}$, $\{3,4,7\}$, $\{3,5,6\}$. This construction is known as the Fano plane.
- The Fano plane is a projective plane over $\mathbb F_2$, and we can generalize the construction to any finite field $\mathbb F_q$. Here, $q$ must be a prime power, and $k$ will be $q+1$.
- When $k-1$ is not a power of a prime, it is an open problem to show that no constructions exist. (We know that $k-1=6$ and $k-1=10$ are impossible as of 1989, and haven't managed to even deal with $k-1=12$ since then.)
Best Answer
Algebraic graph theory.
Within the field of discrete mathematics one often treats the topics of graph theory and combinatorics. These two fields have some overlap as combinatorics is used within graph theory and provides examples for it. Combinatorics mostly deals with counting, both as a means to an end and for the sake of counting. Think of inclusion-exclusion, recursions and counting problems. Graph theory often gets linked to Euler, how he used this approach to solve many problems. It is essentially about graphs and their properties.
A useful tool within these fields (and many others) is algebra. Algebraic refers to the fact that methods from algebra are mainly applied to a particular field or topic. Take for instance algebraic topology, algebraic geometry, algebraic combinatorics and algebraic graph theory. Algebra is an immensely powerful tool, and, in itself a very interesting abstract topic to study.
I therefore think that you are doing algebraic graph theory.