Graph Theory Previous Year Questions (PYQs) for GATE CS: 3+ Solved Questions with Step-by-Step Solutions

1. Towns $A$, $B$ and $C$ are connected to each other by several roads, with at least one road connecting each pair. It is given that, in total, there are 33 roads from $A$ to $B$, including those via $C$. Similarly, there are 23 roads from $B$ to $C$, including those via $A$. How many routes from $A$ to $C$, including those via $B$?

There are 5 friends $A,B,C,D,E$. Because of a heated argument not all of them are on speaking terms anymore. The array below describes who is talking to whom. A value of 1 indicates that the pair is on speaking terms, while a 0 indicates that they are not.

1. Consider a city with $n$ East-West Streets (EWS) and $n$ North-South Avenues (NSA). The EWS are the line segments $\{y=j\mid 1\le j\le n\}$ for all $j\in \{1,2,\dots ,n\}$ and the NSA are the line segments $\{x=i\mid 1\le i\le n\}$ for all $i\in \{1,2,\dots ,n\}$. A junction is a pair $(i,j)$ where avenue $i$ intersects street $j$. How many junctions are there in the city?