The OP contains the specifications

do not immediately involve graph theory, on the surface,

reduce, after a little translation, into a common problem in graph theory (find a matching, find a colouring...).

there should be a "haha!" effect for the mathematician, and a sigh of relief for the programmer.

The following is about as trivial as can be (even in a technical sense of 'trivial': it is based on what is sometimes presented in introductory graph theory lectures as the 'First Theorem of Graph Theory'), but it fits each of the three specifications above:

**To find the number of undirected connections in a finite network of which you only have knowledge in the form of a photograph**. $\hspace{150pt}$(problem)

That is: imagine a situation in which a programmer faces the task of programming a camera-equipped machine to 'look' at such a photograph and correctly output the total number of connections.

To make the problem-description consistent with the 'worked example' below, imagine the company running the search engine which kindly ran for me a Gilbert--Erdős–Rényi-random graph simulation, decides to *empirically test that the number of connection shown on the screen of users equals the number of connections that the search engine returns as a numeral when asked to do so. For the sake of argument, suppose that the company will have none of 'formal verification' of code (though I think this would give greater security) but has resolved to test this very very empirically, by filming a screen. To reach usefully large sample sizes, **they will have to teach a camera-equipped machine how to count the lines**.

Among the "first, naive algorithms that spring to mind to solve this (finite) problem" (to quote the OP) is an "awkward" one: to rasterize the picture, to systematically scan it, to code-up some recognition-of-elongated-shapes, to keep track of what elongated shape you already have counted, to finally somehow arrive at an estimate of the number of connections. (Also note: this approach does not involve any necessary check of correctness, however weak, unlike the approach I am proposing; see the remark at the very end.)

I think that, especially if the photograph is messy, the input data to the machine "[does] not immediately involve graph theory,".

Now comes the "little translation, into a common problem in graph theory", namely into what is arguably the **most trivial of all graph theoretic problems**:

to find the number of edges of a specified graph.

And this problem ("aha!" goes the mathematician, while the programmer heaves the required "sigh of relief") reduces to simply *'doing a sum' of natural numbers* (plus a little pattern recognition, though not a recognition of elongated/curvilinear shapes anymore): the problem reduces to summing the *degree sequence* of the relevant graph.
(The reason is what is whimsically called 'The Handshaking Lemma', or a little presumptiously called 'The First Theorem of Graph heory'^{1})

More precisely, we *idealize* (and what an important, mathematical activity this is: *idealizing sense-data*) the situation, by imagining that there is an abstract graph.

Now we know what to teach the machine:

(0) identify all 'vertex-like' points of the photograph,

(1) 'cookie-cutter' a small circle-shaped portion around each such 'point',

(2) **forget** the vast majority of the 'photograph',

(3) collect the 'cookies' (the order and position of the 'cookies' is **irrelevant**, any data-structure which keeps the set of the 'cookies' will be serviceable),

(4) now solve a *much easier* patter-recognition-problem, on each of the 'cookies': to *recognize the number of 'rays' in the 'star-like' shapes* (there will be *noise*, yet I am confident that this task can be *routinely* done, reliably, by methods of Computational Homology, methods which were more-or-less *made* for doing precisely this: extracting meaningful integer-valued invariants from noisy black-and-white-pictures.
If not, I am confident that this task will be routine for people working in machine-learning/pattern-recognition.)

To summarize: where was the graph-theory here?

On "the surface", a messy photograph of a tangle of connections in a network does *not* look like a graph.
At the very least, I am sure that a person not knowing *concepts* of graph theory would, when having to teach a machine what to do with the sense-data fed to it, be **more** likely to code-up a 'rasterize-and-scan-the-whole-picture-and-invent-heuristics-to-recognize' approach than taking the **graph-theoretically-informed 'cookie-cutter' approach**.

**Worked Example.** Let the given 'photograph' be the network-like part of the following photograph, taken from the webpage of a known search-engine, with the 'order' given to the engine shown in the first line of the image:

Insert now a "haha!" and "sigh of relief".
**No** pattern-recognition of 'line-like' shapes is necessary; it suffices to identify the 'vertex-like' parts of the image, and then do the following:

First the 'cookie-cutting' (here, I use counterclockwise ordering):

Now follows *a* conversion of the 'gray-scale cookies' to something combinatorial (essentially: (0,1)-matrices, given as a black-and-white rid). The diaphanous blue regions do not carry any information; they associate each gray-scale 'observation' with the corresponding (0,1)-matrix, yet this association could be done by the mind of the observer unaided by the blue regions, for the correspondence is quite uniquely determined.

These '0-1-matrices' weren't 'made-up': I had the 'GIMP' software compute it for me, via the "Indexed Color Conversion" functionality, with the option "Use black and white (1-bit) palette" and with "Color-dithering: Floyd-Steinberg (normal)" turned on.
What I give here should even be quite a 'reproducible experiment'.
It should be possible to have a machine produce the same '0-1-matrices' from the gray-scale pictures.

Now insert here some expert advice of someone more versed in computational homology (or some other suitable method: something via eigenvalues of the black-and-white matrices perhaps (though these eigenvalues will not be real-valued? using some appropriate heat-flow?); or someone more versed in *machine-learning/pattern-recognition* algorithms^{2}) than the writer of these lines (who only had to learn computational homology for an exam a few years ago, yet does not work with it), telling us which "Sooo much time"-saving out-of-the-box routine we should use to count the number of 'rays' in the 'star-shaped' matrix-pictures, and now the following numbers come pouring forth:

3 2 6 5 3 4 4 5 7 4 1

Now the so-called *First Theorem of Graph Theory* completes the "reducing" of the problem to a "graph theory algorithm": it remains to calculate

$\frac12\cdot (3 + 2 + 6 + 5 + 3 + 4 + 4 + 5 + 7 + 4 + 1) = \frac12\cdot 44 = 22$

to know (by the 'First Theorem of Graph Theory') that this is the number of edges(=connections) in the 'photograph' of the random graph.

This was a reduction, of sorts.

On which side of your "fine line" this is, I cannot know in advance. By the way, I agree with Dirk Liebhold's comment, that this is *very context-dependent* question, any answer will be 'tainted' by context.

**Addition.** Another small contribution of graph theory in solving this problem:

If the above sum (in the example it was 44) does **not** come out **even**, then something **somewhere** must have gone wrong.

In that sense, the 'First Theorem of Graph Theory' also give a very weak 'check'/'necessary condition' for the correct execution of the algorithm. One of course is not told by the criterion where and why an error has occurred, only that *somewhere* something has gone wrong. Also, if the sum comes out **even**, this, needless to say, does not imply that it is the correct one.

^{1} _{Incidentally, this commonly encountered designation is not only a little presumptious, but also technically-wrong if very
strictly construed: in the strictest sense, 'Graph Theory' is the theory, in the model-theoretic sense, of the class of irreflexive symmetric relations on a set, and, as such, has a one-element signature consisting of a single binary relation symbol. The so-called 'First Theorem of Graph Theory', though, uses a larger signature: which exactly, depends on your formalization, but you can argue that it uses the signature $(\sim,\mathrm{deg},+,\Sigma,\lVert\cdot \rVert)$, where $\sim$ is the binary relation symbol, and $\mathrm{deg}$ and $\lVert\cdot\rVert$ are unary function symbols, the intended interpretation of the former being the degree of its argument, the one of the latter being the number of edges of its argument. }

^{2} _{It would be a nice example of focused interdisciplinary work if someone who knows more about pattern recognitino would leave a relevant comment on what is considered the best method to count the number of 'rays' in the 'star-shaped' '0-1-matrices'. One can for example first 'blow-up' each pixel until the 0-th Betti number (=number of connected components) has become equal to 1, upone which, in a sense, the 'noise' is 'gone', and then one has to come up with a functorial method to 'count the number of bumps along the perimeter'. Ideally, the present answer would in the end feature a completely 'synthetic' method of counting the number of connection in a 'photograph' of a 'network', that is, by 'putting together' existing concepts. }

How complicated can structures be?. Nieuw Archief voor Wiskunde 5/9 nr. 2 June 2008], Jouko Väänänen, somewhat surprisingly decided to use the NP-completeness of $\text{3-colorability}$ to simply write: "The famous P=NP question, one of the Clay Millenium Questions, asks if we can decide in polynomial time whether a given finite graph is 3-colourable." Full stop. He just uses a 'representative'. $\endgroup$ – Peter Heinig Sep 26 '17 at 17:23maximum matching' completely 'rules' the winning strategies) is the well-known PathGame that I described in this MO thread. Admittedly, this is not a number-theoretic example, rather a game-theoretic one.[...] $\endgroup$ – Peter Heinig Sep 26 '17 at 17:33