Year 12 Graph Theory: Properties of graphs
Back to Graph Theory tutorialsGraph properties describe the network as a whole rather than focusing on one individual vertex. This is where graph theory starts to feel more structural: instead of asking only "what is connected to what," we begin asking whether the graph is connected, complete, simple, weighted, or otherwise classified by its overall behaviour. These labels are powerful because they summarise a large amount of information in a single idea. Once the correct property is identified, many later conclusions follow quickly.
Subtopic 1: Connected and disconnected graphs
A graph is connected if every vertex can be reached from every other vertex by some path. If this is not true, the graph is disconnected. This is one of the most useful first checks because connectivity immediately determines what kinds of path and route questions even make sense. If a graph is not connected, then some shortest-path questions have no answer at all between certain vertices.
Worked example 1
- If the graph were connected, every vertex could be reached from every other vertex.
- Vertices in one cluster cannot reach vertices in the other cluster.
Subtopic 2: Simple, complete, and weighted graphs
Other important whole-graph properties include whether the graph is simple, complete, or weighted. A simple graph has no loops and no multiple edges between the same two vertices. A complete graph has an edge joining every pair of distinct vertices. A weighted graph attaches values such as distances, costs, or times to edges. These labels affect how problems are solved because they tell you what information is available and what methods are appropriate.
Worked example 2
- Every pair of distinct vertices is joined.
- That is exactly the definition of a complete graph.
Why graph properties help
Whole-graph properties are useful because they compress a lot of information. If a graph is complete, you instantly know every degree without tracing every edge individually. If it is disconnected, you know that certain routes or circuits across the whole network are impossible. If it is weighted, you know that counting edges alone will not settle route questions. This is why naming properties early is such a strong habit in graph theory: it narrows the problem quickly.
Worked example 3
- A weighted graph measures path length using edge weights, not just edge count.
- A route with fewer edges may still have a larger total weight.
- A route with more edges can be shorter if its total weight is smaller.
From local to global structure
Many graph properties are built from local information. Connectivity depends on the existence of paths. Completeness can be recognised from universal adjacency. Simplicity depends on how individual edges are allowed to behave. This relationship between local and global structure is one of the main themes of graph theory. You learn small facts at the vertex or edge level, and then you use them to classify the graph as a whole.
Common traps
- Describing a disconnected graph as connected because one component is internally well linked.
- Forgetting that a complete graph requires every pair of distinct vertices to be joined.
- Ignoring weights when deciding whether a route is shortest.
- Using whole-graph property words casually without checking the exact definition.
Revision focus
In revision, practise classifying graphs quickly from a diagram. Ask: is it connected, complete, simple, weighted, or something else? This kind of early classification often determines the whole method. It also makes longer graph questions less intimidating because you start by turning the picture into a small set of known labels.
It is also useful to explain why a property does or does not apply, not just to name it. That pushes you toward precise definitions and makes your graph-theory language much more robust under exam conditions.