Tagged Questions

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.

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 ...
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 ...
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 ...
25 views

Non-isomorphic Unicyclic Graphs

How many different (non-isomorphic) connected graphs having N vertices, and exactly one cycle comprising K vertices exist?
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 ...
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$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
37 views

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 ...
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 ...
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 ...
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 * ...
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 ...
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 ...
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 ...
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 ...
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 ...
14 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 ...