Classical zero-knowledge proof (ZKP) constructions such as zk-SNARKs and STARKs impose significant prover computation overhead and circuit compilation complexity that limits their accessibility for resource-constrained verifiable credential applications. This paper proposes a graph-theoretic ZKP framework that encodes identity claims as graph colouring witnesses and employs a Sigma protocol over the elliptic curve commitment scheme to prove knowledge of a valid graph colouring without revealing the colouring itself. The proposed construction leverages the NP-completeness of graph 3-colouring to achieve perfect completeness, computational soundness under the discrete logarithm assumption, and honest-verifier zero-knowledge provable by a polynomial-time simulator. The framework is deployed as an Ethereum smart contract on the EVM, using a Pedersen commitment-based hash accumulator for on-chain witness binding and Merkle proof verification for credential revocation checking. Formal security analysis under the universal composability framework establishes composable security against adaptive adversaries. Experimental evaluation on the Ethereum Sepolia testnet demonstrates proof generation in 38 ms and on-chain verification consuming 21,400 gas units, representing a 73% reduction in proving time compared to zk-SNARK Groth16 and a 58% reduction in gas cost compared to STARK proofs.