Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

1
vote
0answers
25 views

Is there an algorithm to find minimum cut in undirected graph separating source and sink

I have an edge-weighted undirected graph and 2 nodes (often called source and sink). I need to find a set of edges of minimum possible weight, which separates these 2 nodes into 2 weak components. I ...
0
votes
1answer
15 views

Relationship between Maximal Independent Set and Minimum Vertex Cover

Prove that $I$ is a Maximal Independent Set of $G(V,E)$ if and only if $V\setminus I$ is a Minimal Vertex Cover of $G(V,E)$. I think that I have managed to prove that the complement of $I$ is a ...
1
vote
0answers
17 views

Proving a game has a winning strategy over a graph $G$ if and only if $G$ has no perfect matching

Two people play a game over a graph $G$ choosing alternately different vertices $v_1,v_2,...$ such that, for every $i>0$, $v_i$ is adjacent to $v_{i-1}$. The last player capable of choosing a ...
0
votes
1answer
29 views

Write a proof to show that $M$ can be colored in with at most $\alpha +1$ colors

Suppose we have a graph $M$ such that the max degree of any vertex is $\alpha$. Write a proof to show that $M$ can be colored in with at most $\alpha +1$ colors. My attempt I am thinking that I ...
0
votes
0answers
17 views

Suppose G and G' are isomorphic and G has m vertices of degree k. Prove that G' has m vertices of degree k

Suppose G and G' are isomorphic and G has m vertices of degree k. Prove that G' has m vertices of degree k. I don't know how to start this one
0
votes
0answers
6 views

What is the name of the problem domain, solution algorithm of a specific shortest path problem?

I'm trying to find materials for gaining deeper insight in a specific type of a shortest path problem. This is a shortest path problem, where several workers have to service some jobs, each job having ...
0
votes
0answers
8 views

Ranking cliques based on edge weights AND node weights

I am looking for existing methods to rank cliques based on both the edge and nodes weights. Up to now, I was summing up the edges' weights, and I would like to leverage the prior probability I have on ...
-1
votes
0answers
22 views

graph without cut vertex such that $i(G)$ > $\frac{n}{2}$

dominating set for a graph $G = (V, E)$ is a subset $D$ of $V$ such that every vertex not in $D$ is adjacent to at least one member of $D$. The domination number $γ(G)$ is the number of vertices in a ...
0
votes
1answer
30 views

Let G be a graph such that $\delta (G) = n(G) − 2$. Prove that $\kappa (G) = \delta (G)$.

I know if $\delta (G) = n(G) − 1$, $\kappa(G) = \delta(G)$ as $G$ is just a complete graph. But, how do I prove it for $\delta(G) = n(G) − 2$?
0
votes
1answer
12 views

Completion of acyclic sub graph

Statement: Given an acyclic subgraph of a connected graph, show that this subgraph can be completed into a spanning tree of the graph. I know that there is a theorem that states that any connected ...
0
votes
1answer
18 views

Proving that any two spanning trees for a graph has the same number of edges

Prove that any two spanning trees for a graph has the same number of edges. Proving by contradiction. Assume that there exists two spanning trees with different number of edges. Take $G$ to be the ...
0
votes
1answer
21 views

Whats the difference between the smallest connected spanning subgraph and a eulerian path?

I personally don't think there is much difference? Apart from for the smallest connected spanning subgraph that the smallest connected subgraph MUST have n-1 edges where n is number of vertices but ...
0
votes
0answers
17 views

Nodes lying on Same Path in Trees

Given a Treen with $n$ nodes and $n-1$ edges, I have to answer $Q$ queries. In every query, I get a list of nodes of size $k$, $n_1, n_2, ..., n_k$. I need to answer the minimum number of paths that ...
0
votes
1answer
25 views

Every connected graph contains at least 2 vertices of the same degree

Theorem:Every connected graph contains at least 2 vertices of the same degree. (In the Finite and Simple Graph Context) What can I do to prove ? Can you give me any suggestion ?
1
vote
1answer
33 views

graph with maximum degree $6$ such that $\frac{i(G)}{γ(G)} < 3$ [on hold]

dominating set for a graph $G = (V, E)$ is a subset $D$ of $V$ such that every vertex not in $D$ is adjacent to at least one member of $D$. The domination number $γ(G)$ is the number of vertices in a ...
1
vote
0answers
11 views

Conway's theorem on the number of orbits on the set of all ordered cycles in a $d$-valent graph

I am trying to understand Conway's theorem on the number of orbits on the set of all ordered cycles in a $d$-valent graph. I quote it from Cycles in graphs and groups by Kantor. Theorem $1$ ...
1
vote
1answer
31 views

Prove that every edge-coloring of $K_{17}$ with $3$ colors contains a monochromatic $K_3$. [duplicate]

Also, Prove that every edge-coloring of $K_6$ with $2$ colors contains at least two monochromatic copies of $K_3.$ I have no idea how to start these problems. What should I do?
1
vote
1answer
42 views

Find the chromatic number of the graph below.

I know the chromatic number can't be 2 because there's a cycle of 5 there. I tried 3 but to no avail. So I assume the answer is 4. But I can't prove that it's four and not three. Can someone help ...
1
vote
1answer
34 views

Graph Theory: Self - Complementary Graphs

I have started reading Graphs and Digraphs by G Chartrand. I'm stuck on the following problem: Let $G_1$ and $G_2$ be self - complementary graphs, where $G_2$ has even order $n$. Now let $G$ be ...
0
votes
0answers
16 views

Graph Matchings Problem

There was A LOT of given information about 8 students doing research papers on 12 books in a library (I simplified it to letters and numbers). The problem wants to know if all students can work ...
0
votes
1answer
25 views

Non-isomorphic Unicyclic Graphs

How many different (non-isomorphic) connected graphs having N vertices, and exactly one cycle comprising K vertices exist?
1
vote
1answer
27 views

Directed Acyclic Graph (DAG) with 3 verices and 3 toplogical orderings

I am trying to create a DAG with 3 vertices and 3 topological orderings. All I can think of to do is the following graph (or the same graph with both edges' directions reversed): This yields 2 ...
0
votes
0answers
22 views

How to find the characteristic polynomial for the following graph G

What is the closed form of characteristic polynomial (adjacency matrix) for the following graph $G$: With the help of eigenvectors, I found that $4$ eigenvalues of $G$ are that of $P_4$ and $6$ ...
1
vote
1answer
17 views

Minimum size of the largest clique in any graph

I need to find the minimum size of the largest clique in any graph which has $V$ nodes and $E$ edges (the same as this question) This looks like an application of Turan's theorem: Let G be any ...
0
votes
0answers
17 views

Inverse of Laplacian Matrix of graph with rows and columns of some index removed

We know that the Laplacian matrix of a graph $G$ is not invertible since the columns sum to $\mathbf{0}$. However, if we remove the row and column indexed by $i$, then the matrix does become ...
0
votes
0answers
10 views

Terminology for a collection of paths

A path in graph theory is a "sequence of edges which connect a sequence of vertices" (from the Wiki page) Let $p_i$ denote a path between two vertices. Define $P = (p_1,\ldots,p_m)$ as a collection ...
0
votes
1answer
36 views

Reducing Hamiltonian Path Problem to Green Path Problem

The Green Path Problem is as follows: given a graph $G$ with $n/2$ green vertices and $n/2$ red vertices, is there a simple path from $v_1$ to $v_n$ that contains every green vertex? The path can ...
0
votes
1answer
26 views

How can we show that the adjacency matrix of a regular graph commutes with its complement

How can we show that the adjacency matrix of a regular graph commutes with its complement? I have read on StackExchange that the adjacency matrix of a regular graph commutes with the adjacency ...
0
votes
1answer
38 views

Computing the Manhattan Distance between two clusters of points. [closed]

We have two clusters of points: c1: (1, 1), (1, 2), (1, 3) c2: (2, 7), (2, 8), (2, 9) I know the Manhattan Distance formula is as follows: $d(a,b) = \sum|b_i - ...
1
vote
1answer
28 views

Proving the number of degrees in a simple graph (Graph theory)

Prove that in a simple graph with at least two vertices there must be two vertices that have the same degree. What i tried Proving by contradiction Suppose that no two vertex have the same degree ...
0
votes
2answers
17 views

Two homeomorphic graphs have $n_i$ vertices and $m_i$ edges, show that $m_1-n_1=m_2-n_2$

If two homeomorphic graphs ($H_1$ and $H_2$) have $n_i$ vertices and $m_i$ edges, show that $m_1-n_1=m_2-n_2$ I know by the degree summ formula $\sum deg(v)=2E$ Proof: Contract both graphs to ...
0
votes
0answers
2 views

$\bar C_i$ form antichain under induced minor relation

$\bar C_i$ is the graph complement of the cycle $C_i$. An induced minor of a graph is obtained from the original graph by a series of vertex deletions and edge contractions. So I want to show that no ...
0
votes
0answers
10 views

BFS and bipartites graphs

I have the lemma Lemma. Let G be a connected graph, and let $L_0$, …, $L_k$ be the layers produced by BFS starting at node s. Exactly one of the following holds: (i) No edge of G joins two ...
0
votes
2answers
42 views

Burnside Lemma and colorings of a $C_{8}$ graph

I'm trying to determine the number of different colorings of the vertices of a cycle $C_{8}$ graph. Suppose I have 10 colors and I suppose I can use every color as much as I want. I consider two ...
0
votes
0answers
12 views

Maximizing a Special Node-weight sum on a Directed Acyclic Graph

Given a Directed Acyclic Graph (DAG) $G=(V,E)$, also satisfying that if $(u,v),(v,w)\in E \implies (u,w)\in E$. For $S\subseteq V$, define the following set $\Gamma(S)=\left\{u \in S, \not\exists ...
2
votes
1answer
63 views

Reducing graph 3-coloring to 10-coloring

I am trying to show that the NP-Complete problem of 3-coloring a graph reduces to the problem of 10-coloring a graph.I have already shown how 10-coloring can be verified in polynomial time, and is ...
1
vote
3answers
56 views

Color the edges of $K_6$ red or blue. Prove that there is a cycle of length 4 with monochromatic edges. [closed]

Color the edges of $K_6$ red or blue. Prove that there is a cycle of length 4 with monochromatic edges. Attempt: I know that i have to... prove that there must be TWO vertices with “red-degree” at ...
0
votes
1answer
18 views

Proof graph theory(length of a path)

In $G$ simple graph every vertex has the degree of $\delta$. Proof, that in $G$ graph there is at most one $\delta$ long path. I think that I should use in some way the Hamilton path, which says ...
0
votes
0answers
6 views

Given M points and a weighted graph G, map the vertices to distinct points to minimize sum(edge_weight*edge_length)

Given an arbitrary undirected weighted graph G with N vertices, and an arbitrary set of M points P in euclidean 3-space, where M>=N, map the vertices to distinct points such that sum(edge_weight * ...
0
votes
1answer
33 views

Single-element version of the Replacement Theorem.

Show that for each pair of bases $B$ and $B'$ of a finite-dimensional vector space $V$, there is a bijection $\phi: B-B' \rightarrow B'-B$ so that for each $x\in B-B'$, the set ...
0
votes
1answer
26 views

Show that in a binary tree, if B is the number of branch points (including the root) and L is the number of leaves, then one has the relation L = 1+B

We have been discussing trees lately, but have yet to even touch on the topic of a binary tree. I understand what a leaf is, but we didn't have one for the term "branch points" Without being 100% sure ...
0
votes
1answer
28 views

Colouring $K_{2s-1}$

Suppose we 2-colour $K_{2s-1}$ such that no vertex has more than one blue edge incident to it, prove that the graph contains a red $K_s$. I've never seen a Ramsey theory question like this and am ...
1
vote
2answers
14 views

Complete bipartite graph from 2 to m points

How can I show that $K_{2,m}$ is planar for all m? I can't even seem to draw $K_{2,2}$ without intersection and if I draw it as a square then it seems to fail to be bipartite as the second set lies ...
1
vote
1answer
13 views

A connected graph $G$ is $k$-edge-connected $\iff$ each block of $G$ is $k$-edge-connected.

A graph $G$ is $k$-edge-connected if every disconnecting set of edges (i.e. edge set D such that $G' = (V, E \setminus D)$ is disconnected) has at least $k$ edges. A block of a graph is a maximal ...
1
vote
1answer
14 views

Number of faces of connected plane graph with cycles

Suppose $G$ is a connected plane graph with at least $g$ edges containing no cycles of length smaller than $g$, then if $f$ is the number of faces and $e$ is the number of edges then prove that $f ...
1
vote
1answer
44 views

On the eigenvalues of “almost” complete graph ?!

Preliminaries: Let $K_n$ be the complete graph on $n$ vertices. $|E(K_n)|=\frac{n(n-1)}{2}$. It's well known that the eigenvalues of $K_n$ are $n-1$ with multiplicity 1, and -1 with multiplicity ...
-1
votes
1answer
43 views

How to prove that each edge of tree is a bridge?

How to prove that each edge of tree is a bridge? My attempt: Tree is a connected graph which has no cycle, and in a connected graph, bridge is a edge whose removal disconnects the graph. Let ...
1
vote
1answer
35 views

Total number of gifts given at the end of a party

The following is true for n guests at a Christmas party: ...
1
vote
1answer
36 views

v1 deg out = zero?

My Attempt Yes it is true. There is one directed edge between two vertices and you can see that there is one vertex that the out-degree is zero. If you want to fix that, you can add a vertex and a ...
12
votes
0answers
179 views

Dynamically two-coloring a finite graph

Let $G=(V,E)$ be a finite graph whose vertices are going to be colored dynamically. More precisely, consider time periods $t \in \left\{0,1,2\ldots,\right\}$ and for each time $t$ and $i \in V$, let ...