Talk:Regular graph

"When the graph is regular with degree k, the graph will be connected if and only if k has algebraic (and geometric) dimension one."

What does this mean?

I'm sorry for the very late reply. The algebraic dimension is the number of times the eigenvalue is a zero of the characteristic polynomial, the geometric dimension is the dimension of the eigenspace. As the adjacency matrix is symmetric, these two dimensions are the same.Evilbu (talk) 13:05, 9 August 2009 (UTC)

I'd much rather see having a section about properites of regular graphs and merging general properties and algebraic properties together. Stdazi (talk) 19:33, 2 June 2012 (UTC)

Is it n*k/2 (should be) - it would be a good addition The ubik (talk) 22:35, 18 September 2012 (UTC)

Shouldn't the existence formula be n>=k-1 (and nk is even)?

For n=1, k can = 2 (loop to itself), and loops are allowed in a regular graph.

For n=2, k can = 3 (loop itself & to the other node)?

Maybe i'm missing something here...

Lilfolr (talk) 14:24, 15 June 2016 (UTC) lilfolr

While I was a graduate student in mathematics, I found a book of mathematical recreations, in French, in the University of Buffalo's math library. It had a chapter on graphs, and it said that a graph is "cubique" if each of its vertices has exactly 3 edges. In modern terminology we would say that a cubic graph is one that is 3-regular.

The book also said that a 4-regular graph is said to be "quadrillé" (quadrille), and it gave a term for a 5-regular graph that I have forgotten. Has anyone else encountered these terms? Sicherman (talk) 15:19, 21 April 2018 (UTC)

:{{ping|Sicherman|p=,}} a late-coming answer: Yes, I've heard `cubic' and `quartic' for 3- or 4-regularity, respectively, and `quintic' for 5-regularity. Now, we have articles for cubic and for quartic graphs, and (already when you put your questions ages ago) a reference to the former in this article. I'll add one to `quartic', but not a specific one to `quintic', since we (now) seemingly do not employ the latter in WP articles. I suppose that higher regularity numbers k also may be denoted by the specific `Latin-English adjectives denoting `of the degree in discussions of polynomials et cetera{{}}'; but I suspect that most graph theorists in general e. g. would speak about sevenregular graphs rather than septic ones. Regards, JoergenB (talk) 21:01, 25 June 2025 (UTC)

This references a paper from 1999. Is this still the state of the art? Do we know anything about the asymptotic complexity of this problem? I didn't write "efficient" because they don't give any complexity results. Also, the numbers in that paper are a bit underwhelming. Do we have any more recent figures on this? Sschuldenzucker (talk) 18:14, 24 June 2019 (UTC)

The existence section now contains an attempt of a short proof. The main contribution to this was [https://en.wikipedia.org/w/index.php?title=Regular_graph&diff=prev&oldid=988787808 made here]. I think that the idea is good, but the result not quite to the point. It also partly would duplicate the treatment under the heading Properties.

I'll try to remedy this, by adding the edge number explicitly under Property, transposing the order of this and the Existence sections, and rewrite the latter. Unhappily, this will leave very little of the contributions of {{ping|Amitavakala|p=,}} I fear, except the main idea, that that section should contain a short motivation. (The alternative would be to find the conditions explicitly in the literature, and just give a reference. Judging from the history of this article, finding this reference may take some work, though. Personally, I also prefer our math articles to contain some short proofs or motivations, when such are easy to provide.) JoergenB (talk) 17:52, 25 June 2025 (UTC)