\documentclass[11pt, a4paper]{article}

% --- UNIVERSAL PREAMBLE BLOCK ---
\usepackage[a4paper, top=1.5cm, bottom=2cm, left=2cm, right=2cm]{geometry}
\usepackage{fontspec}

\usepackage[english, provide=*]{babel}

\babelprovide[import, onchar=ids fonts]{english}

% Set default/Latin font to Sans Serif in the main (rm) slot for a worksheet feel
\babelfont{rm}{Noto Sans}

% Add because main language is not English
\usepackage{enumitem}
\setlist[itemize]{label=-}

% --- PACKAGES FOR MATH & GRAPHICS ---
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{tikz}
\usetikzlibrary{shapes, positioning, arrows.meta, calc}
\usepackage{multicol}
\usepackage{fancyhdr}

% --- CUSTOM STYLING ---
\pagestyle{fancy}
\fancyhf{}
\lhead{\textbf{Edexcel Further Maths: Decision 1}}
\rhead{Chapter 2: Graphs and Networks}
\cfoot{\thepage}

\title{\textbf{Revision Worksheet: Graph Theory}}
\author{Topic: Graphs, Networks, and Planarity}
\date{}

\begin{document}

\maketitle

\section*{Questions}

\begin{enumerate}

    % --- QUESTION 1 ---
    \item 
    \begin{minipage}[t]{\linewidth}
        Define the following terms in the context of graph theory:
        \begin{enumerate}
            \item A \textbf{Walk}
            \item A \textbf{Simple Graph}
        \end{enumerate}
        \vspace{0.1cm}
        \hspace*{\fill} \textbf{[Total: 2 marks]}
    \end{minipage}
    \vspace{0.5cm}

    % --- QUESTION 2 ---
    \item 
    \begin{minipage}[t]{\linewidth}
        A simple graph $G$ has 8 vertices. The degrees (valencies) of the vertices are $3, 3, 4, 4, 4, 5, 5, x$.
        \begin{enumerate}
            \item Explain why $x$ must be an even number.
        \end{enumerate}
        \vspace{0.1cm}
        \hspace*{\fill} \textbf{[Total: 1 mark]}
    \end{minipage}
    \vspace{0.5cm}

    % --- QUESTION 3 ---
    \item 
    \begin{minipage}[t]{\linewidth}
        Calculate the total number of edges in the complete graph $K_{12}$. State the formula used.
        \vspace{0.1cm}
        \hspace*{\fill} \textbf{[Total: 2 marks]}
    \end{minipage}
    \vspace{0.5cm}

    % --- QUESTION 4 ---
    \item 
    \begin{minipage}[t]{\linewidth}
        Explain the difference between an Adjacency Matrix and a Distance Matrix.
        \\[0.5em] % Forces a new line with a bit of space
        \hspace*{\fill} \textbf{[Total: 2 marks]}
    \end{minipage}
    \vspace{0.5cm}

    % --- QUESTION 5 ---
    \item 
    \begin{minipage}[t]{\linewidth}
        \begin{enumerate}
            \item Draw the complete graph $K_4$.
            \item Define a \textbf{Hamiltonian Cycle}.
            \item Write down a Hamiltonian Cycle for $K_4$ using the vertices A, B, C, D.
        \end{enumerate}
        \vspace{0.1cm}
        \hspace*{\fill} \textbf{[Total: 5 marks]}
    \end{minipage}
    \vspace{0.5cm}

    % --- QUESTION 6 (GRAPH A) ---
    \item 
    \begin{minipage}[t]{\linewidth}
        Consider \textbf{Graph A} below:
        
        \begin{center}
        \begin{tikzpicture}[auto, node distance=2cm, thick, main/.style={circle, draw, font=\sffamily\bfseries}]
            \node[main] (1) {A};
            \node[main] (2) [right of=1] {B};
            \node[main] (3) [below left of=1] {C};
            \node[main] (4) [below right of=1] {D};
            \node[main] (5) [below of=4] {E};
            \node[main] (6) [left of=5] {F};

            \draw (1) -- (2);
            \draw (1) -- (3);
            \draw (1) -- (4);
            \draw (2) -- (4);
            \draw (3) -- (6);
            \draw (4) -- (6);
            \draw (4) -- (5);
            \draw (5) -- (6);
            \draw (3) to [out=270,in=180] (6); % Multiple edge
        \end{tikzpicture}
        \end{center}
        
        \begin{enumerate}
            \item Explain why Graph A is \textbf{not} a simple graph.
            \item List the valency of each vertex.
            \item The table below shows the distances (weights) between three towns X, Y, and Z. Draw the distance matrix for this network.
            \begin{itemize}
                \item X to Y: 5 miles
                \item Y to Z: 8 miles
                \item X to Z: 12 miles
            \end{itemize}
        \end{enumerate}
        \vspace{0.1cm}
        \hspace*{\fill} \textbf{[Total: 5 marks]}
    \end{minipage}
    \vspace{0.5cm}

    % --- QUESTION 7 (ISOMORPHISM - COMPLEX) ---
    \item 
    \begin{minipage}[t]{\linewidth}
        Look at the three graphs below:
        
        \begin{center}
        \begin{tabular}{c c c}
            \textbf{Graph 1} & \textbf{Graph 2} & \textbf{Graph 3} \\
            % Pentagon
            \begin{tikzpicture}[scale=0.7, thick, main/.style={circle, draw, inner sep=2pt, fill=white}]
                \node[main] (1) at (90:1.5) {};
                \node[main] (2) at (162:1.5) {};
                \node[main] (3) at (234:1.5) {};
                \node[main] (4) at (306:1.5) {};
                \node[main] (5) at (18:1.5) {};
                \draw (1)--(2)--(3)--(4)--(5)--(1);
            \end{tikzpicture}
            &
            % Star (Pentagon Isomorph)
            \begin{tikzpicture}[scale=0.7, thick, main/.style={circle, draw, inner sep=2pt, fill=white}]
                \node[main] (1) at (90:1.5) {};
                \node[main] (2) at (162:1.5) {};
                \node[main] (3) at (234:1.5) {};
                \node[main] (4) at (306:1.5) {};
                \node[main] (5) at (18:1.5) {};
                % Connect every 2nd vertex to make a star
                \draw (1)--(3)--(5)--(2)--(4)--(1);
            \end{tikzpicture}
            &
            % House with chord (Distinct degrees)
            \begin{tikzpicture}[scale=0.7, thick, main/.style={circle, draw, inner sep=2pt, fill=white}]
                \node[main] (1) at (0,0) {};
                \node[main] (2) at (2,0) {};
                \node[main] (3) at (2,1.5) {};
                \node[main] (4) at (0,1.5) {};
                \node[main] (5) at (1,2.5) {};
                \draw (1)--(2)--(3)--(5)--(4)--(1);
                \draw (3)--(4); % The chord making degrees unequal
            \end{tikzpicture}
        \end{tabular}
        \end{center}
        
        Identify which two graphs are \textbf{isomorphic} and justify your answer by referring to the valencies (degrees) of the vertices.
        \\[0.5em] % Forces a new line
        \hspace*{\fill} \textbf{[Total: 3 marks]}
    \end{minipage}
    \vspace{0.5cm}

    % --- QUESTION 8 (MATRIX) ---
    \item 
    \begin{minipage}[t]{\linewidth}
        A graph is represented by the following adjacency matrix $M$. Draw the graph represented by this matrix.
        \[
        \begin{array}{c|cccc}
             & A & B & C & D \\
            \hline
            A & 0 & 1 & 1 & 0 \\
            B & 1 & 0 & 2 & 1 \\
            C & 1 & 2 & 0 & 1 \\
            D & 0 & 1 & 1 & 0 
        \end{array}
        \]
        \vspace{0.1cm}
        \hspace*{\fill} \textbf{[Total: 3 marks]}
    \end{minipage}
    \vspace{0.5cm}
    
    % --- QUESTION 9 (GRAPH B) ---
    \item 
    \begin{minipage}[t]{\linewidth}
        Consider \textbf{Graph B} below:
        \begin{center}
        \begin{tikzpicture}[auto, node distance=2.5cm, thick, main/.style={circle, draw, font=\sffamily\bfseries}]
            \node[main] (P) {P};
            \node[main] (Q) [right of=P] {Q};
            \node[main] (R) [below right of=Q] {R};
            \node[main] (S) [below left of=R] {S};
            \node[main] (T) [left of=S] {T};
            \node[main] (U) [above left of=T] {U};

            \draw (P) -- (Q); \draw (Q) -- (R); \draw (R) -- (S);
            \draw (S) -- (T); \draw (T) -- (U); \draw (U) -- (P);
            \draw (P) -- (R); \draw (P) -- (S); \draw (Q) -- (S);
        \end{tikzpicture}
        \end{center}
        \begin{enumerate}
            \item Identify a cycle of length 3 in Graph B.
            \item Explain why this graph cannot be a tree.
        \end{enumerate}
        \vspace{0.1cm}
        \hspace*{\fill} \textbf{[Total: 4 marks]}
    \end{minipage}
    \vspace{0.5cm}

    % --- QUESTION 10 (PLANARITY ALG EXPLAIN - MOVED UP) ---
    \item 
    \begin{minipage}[t]{\linewidth}
        The first step of the \textbf{Planarity Algorithm} involves finding a Hamiltonian cycle. Explain why the Hamiltonian cycle is drawn as a regular polygon (a circle of edges) in this algorithm.
        \vspace{0.1cm}
        \hspace*{\fill} \textbf{[Total: 2 marks]}
    \end{minipage}
    \vspace{0.5cm}

    % --- QUESTION 11 (TREE - MOVED UP) ---
    \item 
    \begin{minipage}[t]{\linewidth}
        Draw a tree with 6 vertices.
        \begin{enumerate}
            \item State the number of edges.
            \item Explain why a tree is always a planar graph.
        \end{enumerate}
        \vspace{0.1cm}
        \hspace*{\fill} \textbf{[Total: 4 marks]}
    \end{minipage}
    \vspace{0.5cm}
    
    % --- QUESTION 12 (PLANARITY ALG APPLY - MOVED UP) ---
    \item 
    \begin{minipage}[t]{\linewidth}
        Apply the Planarity Algorithm to the graph shown below.
        \begin{center}
        \begin{tikzpicture}[scale=1.2, thick, main/.style={circle, draw, font=\bfseries}]
            \node[main] (1) at (90:2) {A};
            \node[main] (2) at (30:2) {B};
            \node[main] (3) at (330:2) {C};
            \node[main] (4) at (270:2) {D};
            \node[main] (5) at (210:2) {E};
            \node[main] (6) at (150:2) {F};
            
            % Hamiltonian Cycle
            \draw (1)--(2)--(3)--(4)--(5)--(6)--(1);
            
            % Internal edges
            \draw (1)--(3); % AC
            \draw (1)--(4); % AD
            \draw (2)--(6); % BF
            \draw (2)--(5); % BE
        \end{tikzpicture}
        \end{center}
        \begin{enumerate}
            \item Identify the Hamiltonian cycle used in the drawing above.
            \item List the edges that are currently drawn inside the cycle.
            \item Determine whether the graph is planar. You may deduce this by determining if any edges \textbf{must} cross.
        \end{enumerate}
        \vspace{0.1cm}
        \hspace*{\fill} \textbf{[Total: 6 marks]}
    \end{minipage}

\end{enumerate}

\newpage
\section*{Solutions and Mark Scheme}

\begin{enumerate}
    \item 
    \begin{enumerate}
        \item A finite sequence of edges such that the end vertex of one edge is the start vertex of the next.
        \item A graph with no loops and no multiple edges between the same pair of vertices.
    \end{enumerate}

    \item By the Handshaking Lemma, the sum of degrees must be even ($2 \times$ edges). The sum of the known degrees is $28$. Since 28 is even, $x$ must be even to keep the total sum even.

    \item Number of edges in $K_n = \frac{n(n-1)}{2}$. For $K_{12}$: $\frac{12 \times 11}{2} = 66$.

    \item An adjacency matrix records the number of direct edges between vertices. A distance matrix (or weight matrix) records the weight (cost/distance) of the edges.

    \item 
    \begin{enumerate}
        \item Diagram should show 4 vertices with every vertex connected to every other vertex.
        \item A cycle that visits every vertex in the graph exactly once (and returns to the start).
        \item Example: $A-B-C-D-A$.
    \end{enumerate}

    \item 
    \begin{enumerate}
        \item It contains a multiple edge between vertices C and F.
        \item A:3, B:2, C:3, D:4, E:2, F:4.
        \item Distance Matrix:
        \[
        \begin{pmatrix} 
          & X & Y & Z \\
        X & - & 5 & 12 \\
        Y & 5 & - & 8 \\
        Z & 12 & 8 & - 
        \end{pmatrix}
        \]
    \end{enumerate}

    \item 
    \textbf{Graph 1 and Graph 2 are isomorphic.}
    \begin{itemize}
        \item \textbf{Reasoning:} Both Graph 1 (Pentagon) and Graph 2 (Star) are \textbf{2-regular} (every vertex has a valency of 2). They are both single cycles of length 5.
        \item Graph 3 (House with chord) has two vertices of valency 2 (bottom corners) and two vertices of valency 3 (top corners of square). Because the valencies do not match Graphs 1 and 2, it cannot be isomorphic to them.
    \end{itemize}

    \item 
    \begin{center}
    \begin{tikzpicture}[node distance=1.5cm, main/.style={circle, draw}]
        \node[main] (A) {A};
        \node[main] (B) [right of=A] {B};
        \node[main] (C) [below of=B] {C};
        \node[main] (D) [below of=A] {D};
        \draw (A)--(B); \draw (A)--(C);
        \draw (B)--(C); \draw (B) to [bend left] (C); % Double edge
        \draw (B)--(D); \draw (C)--(D);
    \end{tikzpicture}
    \end{center}
    (Labels A, B, C, D correspond to the matrix rows/cols. Note the double edge between B and C).

    \item 
    \begin{enumerate}
        \item Many answers possible. e.g., $P-Q-R-P$ or $P-S-R-P$.
        \item A tree cannot contain any cycles. Since we identified a cycle, it is not a tree.
    \end{enumerate}

    \item Drawing the Hamiltonian cycle as a regular polygon creates a clear "boundary" that separates the plane into an "inside" region and an "outside" region. This allows us to systematically check if remaining edges can be placed without crossing.

    \item 
    \begin{enumerate}
        \item 5 edges ($n-1$).
        \item A tree contains no cycles, so edges can never cross or enclose regions in a way that forces crossings.
    \end{enumerate}
    
    \item
    \begin{enumerate}
        \item $A-B-C-D-E-F-A$.
        \item $AC, AD, BF, BE$.
        \item \textbf{Planar}. 
        Edges $AC$ and $BE$ cross, so one must move outside. 
        Edges $AD$ and $BF$ do not cross $AC$ or $BE$ directly in a way that prevents resolving the conflict.
        Example valid configuration: $AC$ Inside, $BF$ Inside, $AD$ Inside, $BE$ Outside.
        Check: $BE$ (Outside) connects 2-5. $BF$ (Inside) connects 2-6. No conflict.
        $AC$ (Inside 1-3) and $BF$ (Inside 2-6) cross? Vertex 2 is in range 1-3. Vertex 6 is in range 3-1. Yes, they cross.
        So $BF$ must be Outside.
        New Config: $AC$ (In), $AD$ (In), $BE$ (Out), $BF$ (Out).
        $BE$ (Out 2-5) vs $BF$ (Out 2-6). No cross (share B).
        $AC$ (In 1-3) vs $AD$ (In 1-4). No cross (share A).
        Therefore, graph is Planar.
    \end{enumerate}

\end{enumerate}

\end{document}