As its long ago since Erdős died and mathoverflow is the second best alternative to him (for discussing personal problems), I'd like to start a fruitful discussion about the following problem ...
There exists a (simple unlabeled) graph on 6 nodes with a pair of non-isomorphic edges (i.e., there is no graph automorphism that sends one edge into the other) such that removal of either of them ...
Among the collections of the open problems of Paul Erdős on the website of Professor Fan Chung, there is one called "number of triangle-free graphs". ...
I'm new to graph theory, but a response to a question I asked a while ago introduced me to the concept of expander graphs. A k-regular graph (henceforth "graph") on n nodes has eigenvalues k = λ1 ≥ ...
Can somebody help me to construct two family of finite simple connected graph $G_i$ and $H_i$, $i=1, 2, \cdots,n$ ($n$ possibly large), such that: $1)$ $G_i\ncong H_i$ for $i=1, 2, \cdots, n$ $2)$ ...
It is known that for triangle-free graphs, if they are $d$-regular, then $2d\leq n$, where $n$ is the number of vertices. In words, the degree is less than or equal to the half of the number of ...