Thank you Joel, Greenstone, Stoleg. After more research y'all's comments and answers have helped me figure out just what I needed. Turns out I was over thinking it when it comes to the triggers and the data integrity.

Recap of what was needed:

Patient table: Nothing

Test Table: For each unique foreign key (Patient ID), the Test ID would start over at 1

Sample Table: For each unique composite foreign key (Test ID AND Patient ID), the Sample ID would start over at 1.

• Each patient can have multiple tests
• Each test can have multiple samples
• If I delete a patient then all test and samples are deleted
• If I delete a test then all samples will be deleted
• If I delete all samples of one test OR all tests of one patient then the test OR patient should not be deleted.

Answer:

This is very simple to implement with a trigger and maintain data integrity. Like Joel says, the data is a very direct structure where there can be many samples to one test, many tests to one patient, and only unique patients in the patient table. This allows for the use of cascading to prevent orphans and maintain data integrity. Setting up cascading satisfies all of required bullets. Example by Joel:

...
CONSTRAINT 'FK_TEST__PATIENT' FOREIGN KEY ('patient_id')
      REFERENCES 'PATIENT' ('patient_id') ON DELETE CASCADE
...
CONSTRAINT 'FK_SAMPLE__TEST' FOREIGN KEY ('test_id')
      REFERENCES 'TEST' ('test_id') ON DELETE CASCADE
...

The next part was to have the auto-increment (this is not the built-in auto-inc) reset for each unique key or composite key. This can be accomplished by the use of BEFORE INSERT trigger. (Credit goes to Devart)

This is my modified trigger for my test table:

delimiter $$
CREATE TRIGGER `insert_test_auto_inc`
  BEFORE INSERT
  ON `tests`
  FOR EACH ROW

BEGIN
  SELECT COALESCE(MAX(`Test ID`) + 1, 1) INTO @`Test ID` FROM tests WHERE `Patient ID` = NEW.`Patient ID`;
  SET NEW.`Test ID` = @`Test ID`;
END
$$

How the trigger code works, starting with the MAX function. The Max of Null is Null and Null + 1 is Null. The COALESCE function returns the first non Null value, so if Test ID is not defined then that is the 1 after the comma. If Test ID is a value, say 1, then it returns it added to one so 1 + 1 = 2. The INTO part puts that value into the user variable @Test ID. The max value is only found for the row that match the Patient ID. This auto-incremented (by code, not built in) value gets written in to the NEW value of Test ID.

This is my modified trigger for my sample table:

delimiter $$
CREATE TRIGGER `insert_sample_auto_inc`
  BEFORE INSERT
  ON `samples`
  FOR EACH ROW

BEGIN
  SELECT COALESCE(MAX(`Sample ID`) + 1, 1) INTO @`Sample ID` FROM samples WHERE `Patient ID` = NEW.`Patient ID` AND `Test ID` = NEW.`Test ID`;
  SET NEW.`Sample ID` = @`Sample ID`;
END
$$

The same thing happens in the sample trigger except it now matches both Patient ID and Test ID using the WHERE statement.

Below are all of the required commands to create this sample database that works just like this question wants. This code was generated using the MySQL Workbench.

    delimiter $$

CREATE DATABASE `testdb` /*!40100 DEFAULT CHARACTER SET utf8 */$$

delimiter $$

CREATE TABLE `patients` (
  `Patient ID` int(10) unsigned NOT NULL,
  `First Name` varchar(45) DEFAULT NULL,
  `Last Name` varchar(45) DEFAULT NULL,
  `DOB` varchar(45) DEFAULT NULL,
  PRIMARY KEY (`Patient ID`),
  UNIQUE KEY `PatientID_UNIQUE` (`Patient ID`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8$$

delimiter $$

CREATE TABLE `tests` (
  `Test ID` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `Patient ID` int(10) unsigned NOT NULL,
  PRIMARY KEY (`Test ID`,`Patient ID`),
  KEY `fk_tests_patient_id_idx` (`Patient ID`),
  CONSTRAINT `fk_tests_patient_id` FOREIGN KEY (`Patient ID`) REFERENCES `patients` (`Patient ID`) ON DELETE CASCADE ON UPDATE CASCADE
) ENGINE=InnoDB AUTO_INCREMENT=7 DEFAULT CHARSET=utf8$$

CREATE
DEFINER=`root`@`localhost`
TRIGGER `testdb`.`insert_test_auto_inc`
BEFORE INSERT ON `testdb`.`tests`
FOR EACH ROW
-- Edit trigger body code below this line. Do not edit lines above this one
BEGIN
  SELECT COALESCE(MAX(`Test ID`) + 1, 1) INTO @`Test ID` FROM tests WHERE `Patient ID` = NEW.`Patient ID`;
  SET NEW.`Test ID` = @`Test ID`;
END
$$
delimiter $$

CREATE TABLE `samples` (
  `Sample ID` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `Test ID` int(10) unsigned NOT NULL,
  `Patient ID` int(10) unsigned NOT NULL,
  `Count Value` int(11) DEFAULT NULL,
  PRIMARY KEY (`Sample ID`,`Test ID`,`Patient ID`),
  KEY `fk_samples_test_id_idx` (`Test ID`),
  KEY `fk_samples_patient_id_idx` (`Patient ID`),
  CONSTRAINT `fk_samples_patient_id` FOREIGN KEY (`Patient ID`) REFERENCES `patients` (`Patient ID`) ON DELETE CASCADE ON UPDATE CASCADE,
  CONSTRAINT `fk_samples_test_id` FOREIGN KEY (`Test ID`) REFERENCES `tests` (`Test ID`) ON DELETE CASCADE ON UPDATE CASCADE
) ENGINE=InnoDB AUTO_INCREMENT=4 DEFAULT CHARSET=utf8$$

CREATE
DEFINER=`root`@`localhost`
TRIGGER `testdb`.`insert_sample_auto_inc`
BEFORE INSERT ON `testdb`.`samples`
FOR EACH ROW
-- Edit trigger body code below this line. Do not edit lines above this one
BEGIN
  SELECT COALESCE(MAX(`Sample ID`) + 1, 1) INTO @`Sample ID` FROM samples WHERE `Patient ID` = NEW.`Patient ID` AND `Test ID` = NEW.`Test ID`;
  SET NEW.`Sample ID` = @`Sample ID`;
END
$$

delimiter ;