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

0
votes
0answers
8 views

What are $r(\Lambda)$ and $s(\Lambda)$?

Proposition 7.2 in Biggs Algebraic Graph Theory book says that $$\det A=\sum (-1)^{r(\Lambda)} 2^{s(\Lambda)},$$ where $A$ is the adjacency matrix of a graph $\Gamma$ and the summation is over all ...
0
votes
1answer
10 views

Prove that the genus $\gamma(G) \leq cr(G)$ for every graph $G$

a) Prove that $\gamma(G) \leq cr(G)$ for every graph $G$ b) Prove that for every $k \geq 1$, there exist a graph $G$ such that $\gamma(G)=1$ and $cr(G)=k$ Let $G$ be a graph of order $n$, size $m$ ...
1
vote
1answer
21 views

combinatorics digraph question

A digraph $G = G(V,E)$ on the set of vertices $V$ is a graph where every edge $e ∈ E$ is directed. (Note that double arrows are not allowed in a digraph.) How many digraphs on $n$ vertices are there? ...
3
votes
0answers
44 views

Every tree has two leaves. Is my proof ok?

A tree is a connected acyclic graph. A leaf is a vertex of degree one. The distance $d(u,v)$ between two vertices $u$ and $v$ of a graph is the length of the shortest path from $u$ to $v$. Theorem. ...
3
votes
0answers
34 views

Transpose of the adjacency matrix

As homework I had to do an adjacency matrix for the following graph: My solution was the following: $$ \begin{bmatrix} 0&0&1&0&0 \\ 1&0&0&1&0 \\ ...
1
vote
1answer
27 views

Wheel Graphs and Dimension of Embeddings

I'd like to preface this by saying this is the tip of the iceberg for an optional question for a summer REU program application, so if you think asking this question is in bad taste, let me know and I ...
-6
votes
0answers
36 views

Example of graph pebbling number and significance

According to the Wikipedia article on graph pebbling: Graph pebbling is a mathematical game and area of interest played on a graph with pebbles on the vertices. 'Game play' is composed of a ...
1
vote
1answer
38 views

What is $\langle I\rangle$ in this text?

I've read the following: It is easy to see that given any independent set $I$ in $V$, the vertices of $V-I$ form a covering of $G$. Conversely, if $V-I$ forms a covering, then $\langle I\rangle$ ...
1
vote
1answer
32 views

All the combination of cycles of consecutive numbers [on hold]

Let say that we have $N$ consecutive number $1,2,...,N$ and we want to find all the possible consecutive number cycles of length $2n+1$. For example: $$\begin{align}&N = 5\\&n = 3\ \ \ \ ...
0
votes
1answer
21 views

Randomized Algorithm for finding perfect matchings

I'm stuck on some of the theory in these notes, i'm trying to learn about randomized algorithms in general and am currently stuck on some notes regarding perfect matchings. Here is a link to the ...
2
votes
1answer
14 views

Relation between number of tree edges in graph with $n$ vertices and $k$ components.

It's a sort of given in my book without any proof that : $$t=n-k$$ where, $t$ = the number of tree edges $n$ = number of vertices $k$ = number of components. Can someone explain me the ...
5
votes
1answer
60 views

Almost every graph is asymmetric?

Here is a question: If i choose at random an isomorphism class of graph(no loops, undirected) on n vertices(with uniform probability on the set of such isomorphism classes), is the probability that ...
1
vote
1answer
23 views

Nearest neighbour algorithm (or so I think).

The algorithm is as follows: Given a graph, we start with some arbitrary vertex, in this vertex the path starts. From a vertex we are at we proceed to a neighbour vertex along some edge, we're keeping ...
1
vote
0answers
7 views

Show that a comparability graph is perfect.

Show that a comparability graph is perfect. I'm trying to be able to prove Dilworth's Theorem from perfect graphs. I'll cite the perfect graph theorem for the complement step. This is the part ...
2
votes
1answer
25 views

Adding an edge and a vertex to non-isomorphic graphs

Let $G$ and $H$ be two non-isomorphic simple graphs of equal order and equal size. Suppose I am to add a vertex $v$ and and edge $e$ incident to $v$ to $G$ and $H$. By add I mean to connect $v$ to ...
1
vote
2answers
27 views

Complement of a bipartite graph

What constraint must be placed on a bipartite graph G to guarantee that G's complement will also be bipartite? I see someone saying that it can't be 4 or more in each group, but I don't see why. I ...
2
votes
1answer
30 views

Network Theorem

Our Electrical Engineering professor told us about this formula relating to circuits: $$Network \ Theorem: \ \ \ \ b = m+n-1$$ where $b$ = number of branches in circuit, $m$ = number of closed ...
0
votes
0answers
26 views

Clique cycles structure

I am currently going through the paper "Covering two-edge-coloured complete graphs with two disjoint monochromatic cycles" by Peter Allen (http://www.ime.usp.br/~allen/twocycle.pdf) and I have some ...
2
votes
1answer
21 views

Difference of two graphs

Given two graphs $G_{1}$ and $G_{2}$ what exactly is the definition of $G_{1}-G_{2}$ used in the Diestel book? Most operations on graphs are clearly defined apart from this one.
0
votes
1answer
13 views

Spectral gap vs. algebraic connectivity

Can someone please clarify how the spectral gap of a graph relates to its algebraic connectivity (aka Fiedler value) and whether these use the adjacency matrix or laplacian matrix?
0
votes
0answers
8 views

Can anyone help to find an algorithm to change a randomly colored map to one where no same color is near using only swaping?

The main Codition is that only swaping color between states in allowed
0
votes
1answer
18 views

How many undirected graphs are possible with $4$ labelled vertices such that exactly $1$ edge is present?

I have drawn the graph and the result is $6$ graphs are possible. A simple graph can have a maximum of $\Large\binom{n}{2}$ edges and each edge can exist or not exist. Therefore, ...
2
votes
1answer
28 views

Chromatic number and vertex covering number

For any graph $G=(V,E)$ let $\tau(G)$ be the minimum cardinality of a vertex cover of $G$. Let $\chi(G)$ denote the chromatic number of $G$. Is there a graph $G$ with $\tau(G) < \chi(G) - 1$?
0
votes
2answers
36 views

Discrete maths proving a random observation

Suppose you had 6 points. Each point can choose to either visit another point, or choose not to visit another point. However, it can't visit itself. In addition, visiting another point works in both ...
0
votes
0answers
22 views

Reference for the proof of interlacing of eigenvalues of submatrices

If one has a $n \times n$ Hermitian matrix $A$ and one removes $k$ of the rows and their corresponding columns then the eigenvalues of the remnant interlace the eigenvalues of the full matrix. Can ...
0
votes
0answers
15 views

How do I find point locations on a graph from edges and one known point position?

I have been given a collection of nodes and edges such that each node connects to every other node by an edge. All the edge lengths are known. One of the nodes locations (x,y) is known, but the rest ...
0
votes
2answers
18 views

Why does list coloring provides a more general setting to discuss the chromatic number?

I'm reading the Handbook of Graph Theory. It says the following: And a little before, the definitions of Chromatic Number: I don't understand what is this generality. Why the list ...
4
votes
3answers
68 views

Outline for high school combinatorics class?

I am a high school student and I have taken all the math classes that my school provides (through calculus AB). I have been looking at a possible independent study for next year and I have landed on ...
1
vote
0answers
29 views

Expected size of largest weakly connected component?

Given an undirected graph of n vertices and n randomly assigned edges, one edge from each vertex, what is the expected size of the largest connected component? For example, with four vertices, there ...
3
votes
2answers
66 views

Finite groups and topological spaces

Can we connect topological spaces with groups as: For topological space $X$ take biective homomorfisms $\phi: X\to X$, then divide such homomorphisms on classes of equivalency $\phi_1 \equiv\phi_2$ ...
2
votes
2answers
28 views

Matching Algorithm in Graph Theory

Given $n$ people, $k$ out of which own a car. We need to match a car for each person without a car. Conditions: Each car fits $5$ people, including the driver. Each driver will only allow his ...
1
vote
0answers
25 views

Are there any programs like family echo that I can use to map mathematics?

Family echo is an online program that allows one to make a family tree, if nothing is clicked it shows most of the family tree as it is, but if one clicks a name one can see clearly all the ancestors ...
0
votes
1answer
28 views

Factor of a Graph

Is $K_{2n}$ $2$-factorable? Illustrate with an example. $K_4$ is $2$-factorable but at many places it is generalized that $K_{2n}$ is not $2$-factorable. Is saying that a $2$-factor exists in a ...
-1
votes
0answers
23 views

Min. color $N$ if every $4$ vertex subgraph has a $3$ degree vertex [duplicate]

If a graph has $N$ vertices and every $4$ vertex subgraph has a $3$ degree vertex then prove there is a vertex with degree $N-1$.
2
votes
1answer
24 views

What is this binding function?

I'm reading the Handbook of Graph Theory. What is binding function (I mean, what function is it? $2x?$ $2x+x^2?$)? It says that it's a function $f:\mathbb{N}\to\mathbb{N}$ and it might have ...
2
votes
0answers
22 views

Check if graphs are Eulerian

I've been checking whether these graphs are Eulerian; I've come to conclusion that all of them are Eulerian, because they're all connected and all the vertices are of even degree. However, when I ...
3
votes
0answers
56 views

Combinatorics project ideas for high school students

It's that time again! Last year I asked for high school project ideas in the area of algebraic geometry, this year it's combinatorics (you can include graph theory and combinatorial game theory if you ...
2
votes
1answer
30 views

$3$-edge coloring of Georges Graph

Accoring to Wolfram|Alpha, Georges Graph $\hskip1in$ is 3-edge colorable. Does anybody have a actual 3-edge coloring in form of three sub-matrices of the adjacence matrix: $$A_1+A_2+A_3=A $$ I ...
1
vote
1answer
13 views

Proof by induction that for a complete simple and undirected graph that $|E|=\frac {n(n-1)} 2$

Prove with induction that for a complete simple and undirected graph that $|E|=\frac {n(n-1)} 2$ Base case is trivial. Suppose that for a graph with $n-1$ vertices we have $|E|=\frac ...
4
votes
0answers
22 views

Hamiltonian cycle and Euler Cycle. [duplicate]

When $G = K_n, n \ge 3$ and $n$ is odd, then from the edges of the $G$ can be built edge-disjoint Hamiltonian cycles. Is it true?
0
votes
1answer
19 views

Network/graph theory -acyclic problem [closed]

Consider an acyclic directed network of n vertices, labeled $i=1...n$, and suppose that the labels are assigned such that all edges run from vertices with higher labels to vertices with lower. Show ...
0
votes
0answers
38 views

The triangle inequality for shortest paths of graphs

In why-the-triangle-inequality I found the statement: for example if $d(a,b)$ measures the "length" of the "shortest path" between points $a$ and $b$ (and this can be interpreted quite ...
0
votes
1answer
29 views

Prove: if the complementary graph is connected, then graph isn't necessarily unconnected.

I have such a question. There is a theorem related to graphs that says, that if a graph is disconnected then it's complementary graph is connected. But how can I prove that the inverse is not true, ...
0
votes
0answers
18 views

Symbol Identification related to set-theory and graph theory

If $A$ is a set of vertices of a graph $G$ where $A=\{V_1, V_2, V_3,V_4... V_N\}$, then what is the meaning of symbol $|A|$ ? I encountered this problem when I was reading a paper related to directed ...
2
votes
1answer
28 views

What is a graph isomorphism?

I am trying to under isomorphism in graphs, and from what I know, if graph A is isomorphic to graph B, then you could basically just rearrange the nodes in A, while keeping the edges connected the ...
0
votes
1answer
18 views

Is these Trees isomorphic or not?

Is these Trees isomorphic or not? They have same structure but they have different code. Because one of them is minimum code. Thank you for your answers in advance.
1
vote
1answer
43 views

Discrete math - Prove that a tree with n nodes must have exactly n - 1 edges? [duplicate]

I'm new in discrete math. Can someone prove simply that a tree with $n$ nodes must have exactly $n - 1$ edges. I have researched the solution but I haven't founded yet. I know of course, a tree with n ...
5
votes
0answers
77 views
+50

Quotient Groups and Covering Spaces in Painting Hanging

Consider the $1$-out-of-$n$ painting hanging problem: Given $n$ nails in a wall, how can we hang a painting such that upon removal of any nail, it falls. This has a nice interpretation as a problem in ...
0
votes
0answers
24 views
1
vote
0answers
48 views

What is the name of a graph structure with 'ports'?

I am wondering what the name of the following structure is. I might call it the madeup name "graph with ports" but most likely it already has a name that i am not aware of. The interesting thing to me ...