I was reading about The Graph Isomorphism Problem on Wikipedia and the article lists a number of special cases for which the problem can be solved in polynomial time. One of these cases is a graph of bounded degree, i.e.,
the number of incident edges to any node in the graph is bounded by an integer (for the entire graph).
I can't think of a graph that wouldn't be of bounded degree. Can someone give an example or perhaps clarify what the article or definition is saying that I do not understand.
Here is the original Wikipedia article which talks of graphs of bounded degree (although it will probably be unhelpful in answering my question): https://en.wikipedia.org/wiki/Graph_isomorphism_problem#Solved_special_cases.
Here is the Wikipedia article on the degree of a graph: https://en.wikipedia.org/wiki/Degree_(graph_theory).
My best guess at a graph of unbounded degree is something like a Caley digraph for the multiplicative group of positive integers (so any node/integer is connected to an infinite number of nodes/integers), but I am not sure if I understand the definitions correctly.
Best Answer
Of course any finite graph has a bounded degree. What the article means is that if you fix some number $k$, then the graph isomorphism problem for graphs of order $n$ can be solved in time $O(P(n))$, where $P$ is a polynomial which depends on k.
The point is that a general graph of order $n$ could have vertices with degree roughly the size of $n$. But as $n$ grows, if I only look at graphs with max degree at most $5$, then I can solve the graph isomorphism problem in polynomial time. If I change the 5 to 10, then I can still do it in polynomial time, but the polynomial is larger.
The general graph isomorphism problem would require you to let $k$ get larger as $n$ gets larger, so you'd be getting bigger and bigger polynomials as $n$ gets large, i.e. there is no one polynomial which could bound all of them.
Does this make sense?