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
1answer
36 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
15 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
26 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
20 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
9 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
37 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
26 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
16 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
62 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
55 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
17 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
31 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
24 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
27 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
12 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
31 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
40 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
35 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 ...
11
votes
0answers
160 views
+50

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 ...
2
votes
1answer
23 views

Question about theorem with trees

I know the theorem: for an undirected graph on $n$ nodes, any of the following two imply the third: $G$ is connected $G$ does not contain a cycle $G$ has $n-1$ edges (source) ...
0
votes
1answer
16 views

Showing ${1\over n}\sum|S_i|=O(\sqrt n)$ for $S_i\subset [n]$, $|S_i\cap S_i|\le 1$ for $i\ne j$

Show ${1\over n}\sum|S_i|=O(\sqrt n)$ where $S_i\subset [n]$, $|S_i\cap S_i|\le 1$ for $i\ne j$. A previous question required showing $|E|\le {1\over 2}(\sqrt{t-1}n^{3\over 2}+n)$, for an $n$-vertex ...
2
votes
1answer
29 views

Numbers of matrices satisfying certain property

Initially we're given a fixed sequence $a=(a_1,a_2,...,a_n)$, s.t. $a_i \le n; \forall i\le n$. Now we need to feel a $n \times n$ matrix with ones and zeroes, such that the matrix is symmetric and ...
2
votes
2answers
59 views

Graph to model the order of different tasks in construction

I have this question: During the construction of a house there are certain tasks that have to be completed before another one can commence, e.g., the roof has to be installed before work on ...
0
votes
0answers
13 views

Euler circuit of complete graph

For a complete graph $K_p$ where $p$ is the number of vertices, then if $p$ is odd, every vertex has even degree and so every complete graph with an odd number of vertices has an Euler circuit. But ...
0
votes
0answers
40 views

Boolean function analysis on random graphs?

Random graphs have some properties that are determined in some random way such as edge probabilities in the interval $[0,1]$. Ryan O'Donnell's book "Analysis of Boolean Functions" (2014) has analysis ...
6
votes
0answers
28 views
+50

Heuristics for topological sort

I have a number of modules connected in a Directed Acyclic Graph. My problem is to find an optimal execution order (minimize the total execution time). Any topological sort suffices for a valid ...
0
votes
1answer
20 views

why Powers of adjacency matrix of a graph G are linearly independent?

I have a question. I can't find the answer. Let G be a connected graph and A is adjacency matrix. Why powers of adjacency matrix are linearly independent? how can we show that. I know i-th power of ...
1
vote
0answers
14 views

Chromatic index of complete graphs using line graphs

I'm interested in computing $\chi'(K_n)$ from the relation $$\chi'(K_n)=\chi(L(K_n)),$$ where $L$ denotes the line graph operator. Is there a good argument to do this? (The answer is of course $=n-1$ ...
0
votes
0answers
25 views

When does vertex connectivity equal minimum degree in a random graph? [closed]

I am trying to prove a property about $\kappa(G)$ (vertex connectivity) with certain probability in a random graph. To do this, I want to relate $\kappa(G)$ to the minimum degree $\delta(G)$ of a ...
0
votes
0answers
18 views

Help me to find mixed chinese postman problem (MCPP) complexity

I know that MCPP is NP-Complete. Also, I have problem formulation: Chinese postman problem for mixed graphs. I was given a task to evaluate the number of operations required for a complete re-election ...
0
votes
2answers
31 views

Number of cycles of length 3 on n vertices. Cycles of length 4?

How many cycles of length 3 are possible for a complete graph with n vertices? Cycles of length 4? My first thought for both scenarios was $n \choose 3$ * $\frac{1}{2}$ ->(cycle lengths of 3) and $n ...
2
votes
1answer
22 views

Number of paths of length three in $K_4$

How many paths of length $3$ can be made from $K_4$ where $4$ represents the number of vertices? I believe the answer is $12$ just by counting the number of different combinations of paths with ...
0
votes
0answers
16 views

Let $G$ be a planar graph. Suppose that $V = V_4 \cup V_8$. Prove that if $|V_8| = 12$, then $|V_4| \ge 18$

For each $n \in \mathbb N$, define $$V_n = \{v \in V : d(v) = n\}$$ Proof. Let $G = (V, E)$ be a planar graph. Suppose that $V = V_4 \cup V_8$. Suppose that $|V_8|$ = 12. Since $|V_8| = ...
1
vote
0answers
22 views

Let G be a simple planar graph such that the length of every cycle is at least 8. Show that $|E| \le \frac{4}{3}|V| - \frac{8}{3}$

Here's what I've got so far. I'm stuck on how to proceed. I believe I need to plug back into Euler's formula, but I'm not getting what I'm looking for by doing that. Where is the denominator of $3$ ...
-2
votes
1answer
37 views

Number of paths of length 2 in a complete graph containing n vertices [closed]

How many paths of length 2 does $K_n$ have? Where n is the number of vertices. I initially thought it should just be $n \choose 2$ but was told that was incorrect? Is there something I'm missing ?
2
votes
1answer
29 views

Graph Theory Proof that R(3,4)=9

The attatched is supposed to prove that $R(3,4)=9$ . One line say says there is no red $K_3$ in the two-colouring of $K_8$ What is it talking about?- I can see plenty of red triangles! (with corners ...