Add new edge to Graph and check if total weight is reduced

I’m new to Graphs and I’m trying to solve this problem in Java:

Given a Graph with N nodes and N-1 weighted bidirectional edges, the algorithm must respond YES if a new edge ‘q’ allows to reduce the overall weight of the graph, NO otherwise.

The edge ‘q’ satisfies this condition if there is an edge ‘e’ such that it is possible to replace ‘e’ with ‘q’ leaving the graph connected and decreasing its overall weight.

I implemented the graph with adjacency list:

public class Vertex {
private final int element;
private final Set<Edge> edges; // Collection of edges to neighbors

public Vertex(int element) {
    this.element = element;
    edges = new HashSet<>();
}

public int getElement() {
    return element;
}

public boolean addEdge(Edge edge) {
    return edges.add(edge);
}

public List<Edge> getEdges() {
    return new ArrayList<>(edges);
}
}

Edge class:

public class Edge {
   private Vertex to;
private int weight;

public Edge(Vertex to, int weight) {
    super();
    this.to = to;
    this.weight = weight;
}

public Vertex getTo() {
    return to;
}
...

and a Graph class:

public class Graph {
   private final Set<Vertex> vertices; // Collection of all vertices

   public Graph() {
       vertices = new HashSet<>();
   }

   public List<Vertex> getVertices() {
       return new ArrayList<>(vertices);
   }

   public boolean addVertex(Vertex vertex) {
       return vertices.add(vertex);
   }
}

Is there an algorithm that I can use to solve the problem?

Answer

Given a Graph with N nodes and N-1 weighted bidirectional edges,

Then the Graph is a tree. (Assuming the Graph is connected.) A useful property of trees is that for any two nodes s and t in the tree, there exists a single unique (simple) path between them.

the algorithm must respond YES if a new edge ‘q’ allows to reduce the overall weight of the graph, NO otherwise.

Adding a new edge between two nodes (say, s and t) in a tree creates a cycle. Removing any edge in this new cycle will create a new (connected) graph that is also a tree.

The edge ‘q’ satisfies this condition if there is an edge ‘e’ such that it is possible to replace ‘e’ with ‘q’ leaving the graph connected and decreasing its overall weight.

This condition can only be satisfied if there exists one or more edges in the path from s to t (or t to s) whose weight is greater than the weight of the new edge q. If there are multiple such edges, any of them may be replaced.