Fastest way to help a lay-person understand what a compsci "graph" is?

How about an analogy to a social graph? You have a whole bunch of people and then some of them know each other and others don't. That's a common real-world situation.

If you assume that people's social memory (or sense-of-friendship) is all-or-nothing, then you might say it's an undirected graph (so Alice won't know Bob unless Bob also knows Alice). That doesn't really account for celebrities, Alzheimer's, or parasocial relationships, but it's not a terrible approximation to most small-world social situations.

You can define lots of graph theory concepts this way, like distance (literally "degrees of separation" was first defined for a social graph!) and graph diameter (what's the actual highest possible score in a degrees-of-Kevin-Bacon game if you choose any two people rather than just Kevin Bacon?). You can also describe things like looking for islands (are two people indirectly connected at all, or not?) and how many separate pieces the graph can be partitioned into.

If you don't mind a more risqué example, some epidemiologists have tried to make graphs of sexual relationships in communities, in order to think about how sexually transmitted diseases could spread. This is also a somewhat natural concept and doesn't literally rely on people's memory (as people would, or would not, have been sex partners whether they remember this or not, according to some definition of sexual activity).

But I think the friendship graph would actually work well enough for getting the general idea across. You can also talk about how people want to study this in real life for things like marketing, propaganda, and public health topics!

The social network paradigm works best for me when explaining to new people.

  You know how Facebook tracks your friends, and the friends they have, and friends and friends, well that kind of relationship can be called a 'graph'

Once you talk about that, I then try to get them thinking about things in a different way.. such as:

  Take this cup sitting on this table... we could say that in the same way that two friends are connected.. that the cup is also connected to the table.

  Which means, the cup is two connections away from the floor!

That is a good real world example that people can get..

  Then as you look around the room, look at how things are connected to what they touch... 
  
  It's possible to build a pretty cool graph that represents those connections just by following the paths you can see around the room.

Then you can talk about how that graph is one where things are linked by touch.. and what are other ways we could represent connections... for example, what would it look like to draw a graph of what object can SEE another object. How different that graph would be.

It's enough to get ppl thinking differently and have a high level view of Graphs

When I learned graph theory, the prevailing understanding was that graphs are mathematical abstractions of networks. Most people have an intuitive understanding that there is some underlying principle of connectivity which make "computer networks" and "social networks" similar to each other in some way.

So, focus on networks. If you're a graph theorist and need to talk to lay people, say that you research the underlying mathematics which combine computer networks and social networks into a single topic. You can then follow up by saying, "mathematicians also call this a graph, which has a specific formal definition, but for this conversation, let's just keep calling it a network, and we'll imagine every network can be represented as a bunch of dots connected by lines."

Most lay people are more interested in applications than formal definitions and theorems, so give them some interesting but intuitive problems which are investigated in network theory, like travelling salesman or "chinese postman."

Six degrees of Kevin Bacon: each "person" is a vertex (node), how they're connected (co-star? one directed another? dog sitter?) is an "edge", and the series of connections between you and Kevin Bacon is a path. If you can go from one person to Kevin Bacon, and then back to that one person without repeating any people in-between, that's a cycle.

Two sentences, but the second one is a segue to the more useful parts of graph theory if they are interested.

I just explain it as something that captures the idea of things being related to each other somehow. The things are the dots, and whatever relation you care about (“friends with”, “next to”, “has flight between”, “pairs well with for dinner”) are the lines between the dots. People usually get it when I explain it with things they’re familiar with, which often isn’t tech related.

Cities and roads can be thought of as a graph. So, think of a graph as a map with just cities and roads. Explain that in the context of a graph, a city can be thought of as a node and a road as an edge.

See https://www.artforum.com/events/mark-lombardi-2-195790/

road networks, streets and intersections, streets have distances and speed limits, so they can be used for describing the values on edges concept too.

One way roads also exist, like in graphs.

Social network/graph is something most people are familiar with these days.