We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

The friendship problem on graphs.

Mertzios, G.B. and Unger, W. (2016) 'The friendship problem on graphs.', Journal of multiple-valued logic and soft computing., 27 (2-3). pp. 275-285.


In this paper we provide a purely combinatorial proof of the Friendship Theorem, which has been first proven by P. Erdős et al. by using also algebraic methods. Moreover, we generalize this theorem in a natural way, assuming that every pair of nodes occupies l ≥ 2 common neighbors. We prove that every graph, which satisfies this generalized l-friendship condition, is a regular graph.

Item Type:Article
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Date accepted:03 October 2014
Date deposited:02 September 2016
Date of first online publication:01 August 2016
Date first made open access:01 July 2017

Save or Share this output

Look up in GoogleScholar