Graphs and Networks: Key Concepts for VCE General Mathematics (Units 3 & 4)

Graphs are diagrams that illustrate connections and are useful for representing road maps, electrical circuits, train networks and many other scenarios.
Graphs contain vertices and edges.
A vertex (also called a node) is one of the dots in the diagram; it can be connected to other vertices by an edge or remain unconnected.
An isolated vertex is a vertex that is not connected to any other vertex.
An edge is a line in the diagram that connects vertices.
An edge can also connect a vertex to itself — this is called a loop.

Connected graph: A graph in which every vertex can be reached from any other vertex by following edges; the number of steps can be zero or more.
Complete graph: A graph where every pair of distinct vertices is connected by an edge.
Disconnected graph: A graph that contains at least one vertex that is not connected to any other vertex (i.e., not in the same connected component).
Simple graph: A graph that has no multiple edges between the same pair of vertices and no loops.
These classifications help determine properties such as communication routes, circuit redundancy, and network reliability.

Degree of a vertex, denoted $\deg(v)$ , is the number of edges incident to the vertex.
A loop contributes a value of 2 to the degree of the vertex (a loop is considered as twice attached to the vertex).
Degree sum (global property): the sum of the degrees of all vertices equals twice the number of edges, i.e.
$\sum_{v\in V} \deg(v) = 2|E|.$
This fundamental relation underpins many graph results (e.g., handshaking lemma) and is useful for checking consistency of a diagram.

Bridge: An edge whose removal would disconnect the graph (i.e., increase the number of connected components).
In graphs, some edges are bridges while others are part of cycles; identifying bridges helps assess network reliability and vulnerability.
In diagrams, bridges are often highlighted (e.g., red) to emphasize critical connections.

Planar graph: A graph that can be drawn on a 2D plane without any edges crossing, except at shared vertices.
A drawing on the plane partitions the plane into regions called faces.
When drawing planar graphs, the goal is to avoid edge crossings except at vertices, to maintain planarity.

Euler’s rule applies to planar graphs that are connected: $V - E + F = 2,$ where:
- $V$ = number of vertices,
- $E$ = number of edges,
- $F$ = number of faces.
This formula links three basic quantities and can be used to verify the consistency of a planar drawing.
Note: The formula as stated applies to connected planar graphs; it is the standard form used in these materials.

Isomorphic graphs: Graphs that appear different but have the same vertex-edge connections (i.e., an edge-vertex correspondence exists that preserves adjacency).
Subtleties arise depending on whether graphs are labelled or unlabelled.
In the VCE General Maths context, the emphasis is largely on isomorphisms of unlabelled graphs.
Key point: Isomorphic graphs represent the same structural network despite different drawings or vertex labels.

Directed graphs (or digraphs) are formed when each edge has a single direction.
Direction is indicated by an arrowhead on the edge.
This adds orientation information to the connections, which is essential for modelling flows, prerequisites, or dependencies.

Objective: Verify Euler’s rule for a given graph.
Steps generally involved:
- Count the number of vertices $V$ .
- Count the number of edges $E$ .
- Count the number of faces $F$ in the planar drawing (including the outer, infinite face).
- Check whether $V - E + F = 2$ holds (for a connected planar graph).

Task: Draw the graph in planar form (i.e., a planar embedding).
Steps: reposition vertices and route edges to avoid crossings; ensure that any crossing would instead be at a vertex if unavoidable.
Outcome: A planar representation where faces can be clearly counted and Euler’s formula can be applied.pts (Common Questions)

Terms to know:
- Complete graph: every pair of distinct vertices is connected by a unique edge.
- Connected graph: there is a path between every pair of vertices.
- Simple graph: no loops and no multiple edges between the same pair of vertices.
- Degenerate (often used in some questions): typically refers to a graph with minimal structure (context-dependent; may indicate trivial or edge-case situations).
Example type: Given a graph, determine which of the options (complete, connected, simple, degenerate) best describes it. Understanding the definitions helps classify graphs quickly.

Question format: Identify which graph among options is a directed graph (i.e., where all edges have a direction).
Key reminder: In a directed graph, edges must be depicted with arrows indicating direction.

Graphs are diagrams with vertices and edges used to model connections.
A planar graph can be drawn without edge crossings; its drawing divides the plane into faces.
Faces are the regions into which a planar drawing partitions the plane.
Euler’s rule: $V - E + F = 2$ for connected planar graphs, linking vertices, edges, and faces.
Degree of a vertex: $\deg(v)$ is the number of edges incident to the vertex; a loop contributes 2 to the degree.
Degree sum formula: $\sum_{v\in V} \deg(v) = 2|E|.$ This is a fundamental property of any graph.
Bridges are edges whose removal increases the number of connected components.
Planar graphs must be drawn to avoid edge crossings except at vertices.
Isomorphic graphs have the same vertex-edge structure; unlabelled isomorphisms are typically the focus in this course.
Directed graphs (digraphs) assign a direction to each edge, indicated by arrows.
After these topics, the course will introduce Adjacency Matrices as a next topic, followed by deeper treatment of Euler’s rule and related concepts.

Adjacency matrices: a matrix representation of a graph that encodes vertex-to-vertex connections.
Euler’s rule and Euler’s formula: deeper exploration and applications.
Degree sum concepts: practice with counting degrees and validating edge counts.

Terminology and diagrams come from the Edrolo presentation by Michael Palmer (2023) for VCE General Mathematics Units 3 & 4, Chapter 8: Networks and Decision Mathematics.
The material covers foundational graph theory concepts relevant to networks, planar drawings, and directed graphs, with worked examples and practice questions.