So, I read the following Theorem by Matousek and Thomas:
Given graphs $G$ and $H$, we want to check if there is a subgraph $S \subseteq H$ such that $S$ and $G$ are isomorphic.
Then, if the maximum degree of $G$ is bounded by a constant $c$ and if $H$ is a partial $k$-tree, then the Subgraph Isomorphism, and Induced Subgraph Isomorphism problems are solvable in $O(|V(G)|^{k+1} \cdot |V(H)|)$ time.
Now, every graph $G$ (finite) has a max degree that is constant, and every graph $H$ is a partial $k$-tree for some natural number $k$.
And thus, the Subgraph Isomorphism problem for any pair of graphs $G$,$H$ can be solved in Polynomial time.
Then, why is the Subgraph Isomorphism problem classified as an NP-Hard problem?
I do not know the theorem in question but I am pretty sure that $c$ should somehow figure into the runtime. But at any rate, this argument is incorrect:
This is bit like saying that every graph has a number of vertices $n$ that is constant, so an $O(2^n)$ algorithm is polynomial (indeed, constant!).
In general, when we say that an algorithm runs in polynomial time, we have to specify what are the possible inputs, i.e. what is it polynomial in. In the case of graph theory, the input is the description of an arbitrary graph or graphs. Since the size of such a description is polynomial in the number of vertices, we can consider such an algorithm polynomial if its runtime is bounded by a polynomial of the number of vertices of the input graphs.
Now in our case $H$ might be a $(|V(H)|-1)$-tree (if it is complete), so the only bound we can give for $|V(G)|^{k+1} \cdot |V(H)|$ in terms of $|V(G)|$ and $|V(H)|$ is $|V(G)|^{|V(H)| + 1},$ which is clearly not polynomial in the two variables.
However, such an algorithm is valuable in showing, in a sense, where the complexity of the NP-hard problem lies. In this case it shows that if $G$ has small maximum degree and $H$ has small treewidth, then the problem is tractable.